compr_rtime.c 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright (C) 2001-2003 Red Hat, Inc.
  5. *
  6. * Created by Arjan van de Ven <arjanv@redhat.com>
  7. *
  8. * For licensing information, see the file 'LICENCE' in this directory.
  9. *
  10. * $Id: compr_rtime.c,v 1.1.1.1 2007/06/12 07:27:13 eyryu Exp $
  11. *
  12. *
  13. * Very simple lz77-ish encoder.
  14. *
  15. * Theory of operation: Both encoder and decoder have a list of "last
  16. * occurrences" for every possible source-value; after sending the
  17. * first source-byte, the second byte indicated the "run" length of
  18. * matches
  19. *
  20. * The algorithm is intended to only send "whole bytes", no bit-messing.
  21. *
  22. */
  23. #include <linux/kernel.h>
  24. #include <linux/types.h>
  25. #include <linux/errno.h>
  26. #include <linux/string.h>
  27. #include <linux/jffs2.h>
  28. #include "compr.h"
  29. /* _compress returns the compressed size, -1 if bigger */
  30. static int jffs2_rtime_compress(unsigned char *data_in,
  31. unsigned char *cpage_out,
  32. uint32_t *sourcelen, uint32_t *dstlen,
  33. void *model)
  34. {
  35. short positions[256];
  36. int outpos = 0;
  37. int pos=0;
  38. memset(positions,0,sizeof(positions));
  39. while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
  40. int backpos, runlen=0;
  41. unsigned char value;
  42. value = data_in[pos];
  43. cpage_out[outpos++] = data_in[pos++];
  44. backpos = positions[value];
  45. positions[value]=pos;
  46. while ((backpos < pos) && (pos < (*sourcelen)) &&
  47. (data_in[pos]==data_in[backpos++]) && (runlen<255)) {
  48. pos++;
  49. runlen++;
  50. }
  51. cpage_out[outpos++] = runlen;
  52. }
  53. if (outpos >= pos) {
  54. /* We failed */
  55. return -1;
  56. }
  57. /* Tell the caller how much we managed to compress, and how much space it took */
  58. *sourcelen = pos;
  59. *dstlen = outpos;
  60. return 0;
  61. }
  62. static int jffs2_rtime_decompress(unsigned char *data_in,
  63. unsigned char *cpage_out,
  64. uint32_t srclen, uint32_t destlen,
  65. void *model)
  66. {
  67. short positions[256];
  68. int outpos = 0;
  69. int pos=0;
  70. memset(positions,0,sizeof(positions));
  71. while (outpos<destlen) {
  72. unsigned char value;
  73. int backoffs;
  74. int repeat;
  75. value = data_in[pos++];
  76. cpage_out[outpos++] = value; /* first the verbatim copied byte */
  77. repeat = data_in[pos++];
  78. backoffs = positions[value];
  79. positions[value]=outpos;
  80. if (repeat) {
  81. if (backoffs + repeat >= outpos) {
  82. while(repeat) {
  83. cpage_out[outpos++] = cpage_out[backoffs++];
  84. repeat--;
  85. }
  86. } else {
  87. memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat);
  88. outpos+=repeat;
  89. }
  90. }
  91. }
  92. return 0;
  93. }
  94. static struct jffs2_compressor jffs2_rtime_comp = {
  95. .priority = JFFS2_RTIME_PRIORITY,
  96. .name = "rtime",
  97. .compr = JFFS2_COMPR_RTIME,
  98. .compress = &jffs2_rtime_compress,
  99. .decompress = &jffs2_rtime_decompress,
  100. #ifdef JFFS2_RTIME_DISABLED
  101. .disabled = 1,
  102. #else
  103. .disabled = 0,
  104. #endif
  105. };
  106. int jffs2_rtime_init(void)
  107. {
  108. return jffs2_register_compressor(&jffs2_rtime_comp);
  109. }
  110. void jffs2_rtime_exit(void)
  111. {
  112. jffs2_unregister_compressor(&jffs2_rtime_comp);
  113. }