compr_rtime.c 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright © 2001-2007 Red Hat, Inc.
  5. * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
  6. *
  7. * Created by Arjan van de Ven <arjanv@redhat.com>
  8. *
  9. * For licensing information, see the file 'LICENCE' in this directory.
  10. *
  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. {
  34. unsigned short positions[256];
  35. int outpos = 0;
  36. int pos=0;
  37. if (*dstlen <= 3)
  38. return -1;
  39. memset(positions,0,sizeof(positions));
  40. while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
  41. int backpos, runlen=0;
  42. unsigned char value;
  43. value = data_in[pos];
  44. cpage_out[outpos++] = data_in[pos++];
  45. backpos = positions[value];
  46. positions[value]=pos;
  47. while ((backpos < pos) && (pos < (*sourcelen)) &&
  48. (data_in[pos]==data_in[backpos++]) && (runlen<255)) {
  49. pos++;
  50. runlen++;
  51. }
  52. cpage_out[outpos++] = runlen;
  53. }
  54. if (outpos >= pos) {
  55. /* We failed */
  56. return -1;
  57. }
  58. /* Tell the caller how much we managed to compress, and how much space it took */
  59. *sourcelen = pos;
  60. *dstlen = outpos;
  61. return 0;
  62. }
  63. static int jffs2_rtime_decompress(unsigned char *data_in,
  64. unsigned char *cpage_out,
  65. uint32_t srclen, uint32_t destlen)
  66. {
  67. unsigned 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. }