lib/lzo/lzo1x_compress.c

   1 /*
   2  *  LZO1X Compressor from MiniLZO
   3  *
   4  *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
   5  *
   6  *  The full LZO package can be found at:
   7  *  http://www.oberhumer.com/opensource/lzo/
   8  *
   9  *  Changed for kernel use by:
  10  *  Nitin Gupta <nitingupta910@gmail.com>
  11  *  Richard Purdie <rpurdie@openedhand.com>
  12  */
  13
  14 #include <linux/module.h>
  15 #include <linux/kernel.h>
  16 #include <linux/lzo.h>
  17 #include <asm/unaligned.h>
  18 #include "lzodefs.h"
  19
  20 static noinline size_t
  21 _lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
  22                 unsigned char *out, size_t *out_len, void *wrkmem)
  23 {
  24         const unsigned char * const in_end = in + in_len;
  25         const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
  26         const unsigned char ** const dict = wrkmem;
  27         const unsigned char *ip = in, *ii = ip;
  28         const unsigned char *end, *m, *m_pos;
  29         size_t m_off, m_len, dindex;
  30         unsigned char *op = out;
  31
  32         ip += 4;
  33
  34         for (;;) {
  35                 dindex = ((size_t)(0x21 * DX3(ip, 5, 5, 6)) >> 5) & D_MASK;
  36                 m_pos = dict[dindex];
  37
  38                 if (m_pos < in)
  39                         goto literal;
  40
  41                 if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
  42                         goto literal;
  43
  44                 m_off = ip - m_pos;
  45                 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  46                         goto try_match;
  47
  48                 dindex = (dindex & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
  49                 m_pos = dict[dindex];
  50
  51                 if (m_pos < in)
  52                         goto literal;
  53
  54                 if (ip == m_pos || ((size_t)(ip - m_pos) > M4_MAX_OFFSET))
  55                         goto literal;
  56
  57                 m_off = ip - m_pos;
  58                 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  59                         goto try_match;
  60
  61                 goto literal;
  62
  63 try_match:
  64                 if (get_unaligned((const unsigned short *)m_pos)
  65                                 == get_unaligned((const unsigned short *)ip)) {
  66                         if (likely(m_pos[2] == ip[2]))
  67                                         goto match;
  68                 }
  69
  70 literal:
  71                 dict[dindex] = ip;
  72                 ++ip;
  73                 if (unlikely(ip >= ip_end))
  74                         break;
  75                 continue;
  76
  77 match:
  78                 dict[dindex] = ip;
  79                 if (ip != ii) {
  80                         size_t t = ip - ii;
  81
  82                         if (t <= 3) {
  83                                 op[-2] |= t;
  84                         } else if (t <= 18) {
  85                                 *op++ = (t - 3);
  86                         } else {
  87                                 size_t tt = t - 18;
  88
  89                                 *op++ = 0;
  90                                 while (tt > 255) {
  91                                         tt -= 255;
  92                                         *op++ = 0;
  93                                 }
  94                                 *op++ = tt;
  95                         }
  96                         do {
  97                                 *op++ = *ii++;
  98                         } while (--t > 0);
  99                 }
 100
 101                 ip += 3;
 102                 if (m_pos[3] != *ip++ || m_pos[4] != *ip++
 103                                 || m_pos[5] != *ip++ || m_pos[6] != *ip++
 104                                 || m_pos[7] != *ip++ || m_pos[8] != *ip++) {
 105                         --ip;
 106                         m_len = ip - ii;
 107
 108                         if (m_off <= M2_MAX_OFFSET) {
 109                                 m_off -= 1;
 110                                 *op++ = (((m_len - 1) << 5)
 111                                                 | ((m_off & 7) << 2));
 112                                 *op++ = (m_off >> 3);
 113                         } else if (m_off <= M3_MAX_OFFSET) {
 114                                 m_off -= 1;
 115                                 *op++ = (M3_MARKER | (m_len - 2));
 116                                 goto m3_m4_offset;
 117                         } else {
 118                                 m_off -= 0x4000;
 119
 120                                 *op++ = (M4_MARKER | ((m_off & 0x4000) >> 11)
 121                                                 | (m_len - 2));
 122                                 goto m3_m4_offset;
 123                         }
 124                 } else {
 125                         end = in_end;
 126                         m = m_pos + M2_MAX_LEN + 1;
 127
 128                         while (ip < end && *m == *ip) {
 129                                 m++;
 130                                 ip++;
 131                         }
 132                         m_len = ip - ii;
 133
 134                         if (m_off <= M3_MAX_OFFSET) {
 135                                 m_off -= 1;
 136                                 if (m_len <= 33) {
 137                                         *op++ = (M3_MARKER | (m_len - 2));
 138                                 } else {
 139                                         m_len -= 33;
 140                                         *op++ = M3_MARKER | 0;
 141                                         goto m3_m4_len;
 142                                 }
 143                         } else {
 144                                 m_off -= 0x4000;
 145                                 if (m_len <= M4_MAX_LEN) {
 146                                         *op++ = (M4_MARKER
 147                                                 | ((m_off & 0x4000) >> 11)
 148                                                 | (m_len - 2));
 149                                 } else {
 150                                         m_len -= M4_MAX_LEN;
 151                                         *op++ = (M4_MARKER
 152                                                 | ((m_off & 0x4000) >> 11));
 153 m3_m4_len:
 154                                         while (m_len > 255) {
 155                                                 m_len -= 255;
 156                                                 *op++ = 0;
 157                                         }
 158
 159                                         *op++ = (m_len);
 160                                 }
 161                         }
 162 m3_m4_offset:
 163                         *op++ = ((m_off & 63) << 2);
 164                         *op++ = (m_off >> 6);
 165                 }
 166
 167                 ii = ip;
 168                 if (unlikely(ip >= ip_end))
 169                         break;
 170         }
 171
 172         *out_len = op - out;
 173         return in_end - ii;
 174 }
 175
 176 int lzo1x_1_compress(const unsigned char *in, size_t in_len, unsigned char *out,
 177                         size_t *out_len, void *wrkmem)
 178 {
 179         const unsigned char *ii;
 180         unsigned char *op = out;
 181         size_t t;
 182
 183         if (unlikely(in_len <= M2_MAX_LEN + 5)) {
 184                 t = in_len;
 185         } else {
 186                 t = _lzo1x_1_do_compress(in, in_len, op, out_len, wrkmem);
 187                 op += *out_len;
 188         }
 189
 190         if (t > 0) {
 191                 ii = in + in_len - t;
 192
 193                 if (op == out && t <= 238) {
 194                         *op++ = (17 + t);
 195                 } else if (t <= 3) {
 196                         op[-2] |= t;
 197                 } else if (t <= 18) {
 198                         *op++ = (t - 3);
 199                 } else {
 200                         size_t tt = t - 18;
 201
 202                         *op++ = 0;
 203                         while (tt > 255) {
 204                                 tt -= 255;
 205                                 *op++ = 0;
 206                         }
 207
 208                         *op++ = tt;
 209                 }
 210                 do {
 211                         *op++ = *ii++;
 212                 } while (--t > 0);
 213         }
 214
 215         *op++ = M4_MARKER | 1;
 216         *op++ = 0;
 217         *op++ = 0;
 218
 219         *out_len = op - out;
 220         return LZO_E_OK;
 221 }
 222 EXPORT_SYMBOL_GPL(lzo1x_1_compress);
 223
 224 MODULE_LICENSE("GPL");
 225 MODULE_DESCRIPTION("LZO1X-1 Compressor");
 226