kernel/lib/lzo/lzo1x_compress.c

   1 /*
   2  *  LZO1X Compressor from LZO
   3  *
   4  *  Copyright (C) 1996-2012 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 Linux 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 <asm/unaligned.h>
  17 #include <linux/lzo.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,
  23                     size_t ti, void *wrkmem)
  24 {
  25         const unsigned char *ip;
  26         unsigned char *op;
  27         const unsigned char * const in_end = in + in_len;
  28         const unsigned char * const ip_end = in + in_len - 20;
  29         const unsigned char *ii;
  30         lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
  31
  32         op = out;
  33         ip = in;
  34         ii = ip;
  35         ip += ti < 4 ? 4 - ti : 0;
  36
  37         for (;;) {
  38                 const unsigned char *m_pos;
  39                 size_t t, m_len, m_off;
  40                 u32 dv;
  41 literal:
  42                 ip += 1 + ((ip - ii) >> 5);
  43 next:
  44                 if (unlikely(ip >= ip_end))
  45                         break;
  46                 dv = get_unaligned_le32(ip);
  47                 t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK;
  48                 m_pos = in + dict[t];
  49                 dict[t] = (lzo_dict_t) (ip - in);
  50                 if (unlikely(dv != get_unaligned_le32(m_pos)))
  51                         goto literal;
  52
  53                 ii -= ti;
  54                 ti = 0;
  55                 t = ip - ii;
  56                 if (t != 0) {
  57                         if (t <= 3) {
  58                                 op[-2] |= t;
  59                                 COPY4(op, ii);
  60                                 op += t;
  61                         } else if (t <= 16) {
  62                                 *op++ = (t - 3);
  63                                 COPY8(op, ii);
  64                                 COPY8(op + 8, ii + 8);
  65                                 op += t;
  66                         } else {
  67                                 if (t <= 18) {
  68                                         *op++ = (t - 3);
  69                                 } else {
  70                                         size_t tt = t - 18;
  71                                         *op++ = 0;
  72                                         while (unlikely(tt > 255)) {
  73                                                 tt -= 255;
  74                                                 *op++ = 0;
  75                                         }
  76                                         *op++ = tt;
  77                                 }
  78                                 do {
  79                                         COPY8(op, ii);
  80                                         COPY8(op + 8, ii + 8);
  81                                         op += 16;
  82                                         ii += 16;
  83                                         t -= 16;
  84                                 } while (t >= 16);
  85                                 if (t > 0) do {
  86                                         *op++ = *ii++;
  87                                 } while (--t > 0);
  88                         }
  89                 }
  90
  91                 m_len = 4;
  92                 {
  93 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ64)
  94                 u64 v;
  95                 v = get_unaligned((const u64 *) (ip + m_len)) ^
  96                     get_unaligned((const u64 *) (m_pos + m_len));
  97                 if (unlikely(v == 0)) {
  98                         do {
  99                                 m_len += 8;
 100                                 v = get_unaligned((const u64 *) (ip + m_len)) ^
 101                                     get_unaligned((const u64 *) (m_pos + m_len));
 102                                 if (unlikely(ip + m_len >= ip_end))
 103                                         goto m_len_done;
 104                         } while (v == 0);
 105                 }
 106 #  if defined(__LITTLE_ENDIAN)
 107                 m_len += (unsigned) __builtin_ctzll(v) / 8;
 108 #  elif defined(__BIG_ENDIAN)
 109                 m_len += (unsigned) __builtin_clzll(v) / 8;
 110 #  else
 111 #    error "missing endian definition"
 112 #  endif
 113 #elif defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ32)
 114                 u32 v;
 115                 v = get_unaligned((const u32 *) (ip + m_len)) ^
 116                     get_unaligned((const u32 *) (m_pos + m_len));
 117                 if (unlikely(v == 0)) {
 118                         do {
 119                                 m_len += 4;
 120                                 v = get_unaligned((const u32 *) (ip + m_len)) ^
 121                                     get_unaligned((const u32 *) (m_pos + m_len));
 122                                 if (v != 0)
 123                                         break;
 124                                 m_len += 4;
 125                                 v = get_unaligned((const u32 *) (ip + m_len)) ^
 126                                     get_unaligned((const u32 *) (m_pos + m_len));
 127                                 if (unlikely(ip + m_len >= ip_end))
 128                                         goto m_len_done;
 129                         } while (v == 0);
 130                 }
 131 #  if defined(__LITTLE_ENDIAN)
 132                 m_len += (unsigned) __builtin_ctz(v) / 8;
 133 #  elif defined(__BIG_ENDIAN)
 134                 m_len += (unsigned) __builtin_clz(v) / 8;
 135 #  else
 136 #    error "missing endian definition"
 137 #  endif
 138 #else
 139                 if (unlikely(ip[m_len] == m_pos[m_len])) {
 140                         do {
 141                                 m_len += 1;
 142                                 if (ip[m_len] != m_pos[m_len])
 143                                         break;
 144                                 m_len += 1;
 145                                 if (ip[m_len] != m_pos[m_len])
 146                                         break;
 147                                 m_len += 1;
 148                                 if (ip[m_len] != m_pos[m_len])
 149                                         break;
 150                                 m_len += 1;
 151                                 if (ip[m_len] != m_pos[m_len])
 152                                         break;
 153                                 m_len += 1;
 154                                 if (ip[m_len] != m_pos[m_len])
 155                                         break;
 156                                 m_len += 1;
 157                                 if (ip[m_len] != m_pos[m_len])
 158                                         break;
 159                                 m_len += 1;
 160                                 if (ip[m_len] != m_pos[m_len])
 161                                         break;
 162                                 m_len += 1;
 163                                 if (unlikely(ip + m_len >= ip_end))
 164                                         goto m_len_done;
 165                         } while (ip[m_len] == m_pos[m_len]);
 166                 }
 167 #endif
 168                 }
 169 m_len_done:
 170
 171                 m_off = ip - m_pos;
 172                 ip += m_len;
 173                 ii = ip;
 174                 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 175                         m_off -= 1;
 176                         *op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
 177                         *op++ = (m_off >> 3);
 178                 } else if (m_off <= M3_MAX_OFFSET) {
 179                         m_off -= 1;
 180                         if (m_len <= M3_MAX_LEN)
 181                                 *op++ = (M3_MARKER | (m_len - 2));
 182                         else {
 183                                 m_len -= M3_MAX_LEN;
 184                                 *op++ = M3_MARKER | 0;
 185                                 while (unlikely(m_len > 255)) {
 186                                         m_len -= 255;
 187                                         *op++ = 0;
 188                                 }
 189                                 *op++ = (m_len);
 190                         }
 191                         *op++ = (m_off << 2);
 192                         *op++ = (m_off >> 6);
 193                 } else {
 194                         m_off -= 0x4000;
 195                         if (m_len <= M4_MAX_LEN)
 196                                 *op++ = (M4_MARKER | ((m_off >> 11) & 8)
 197                                                 | (m_len - 2));
 198                         else {
 199                                 m_len -= M4_MAX_LEN;
 200                                 *op++ = (M4_MARKER | ((m_off >> 11) & 8));
 201                                 while (unlikely(m_len > 255)) {
 202                                         m_len -= 255;
 203                                         *op++ = 0;
 204                                 }
 205                                 *op++ = (m_len);
 206                         }
 207                         *op++ = (m_off << 2);
 208                         *op++ = (m_off >> 6);
 209                 }
 210                 goto next;
 211         }
 212         *out_len = op - out;
 213         return in_end - (ii - ti);
 214 }
 215
 216 int lzo1x_1_compress(const unsigned char *in, size_t in_len,
 217                      unsigned char *out, size_t *out_len,
 218                      void *wrkmem)
 219 {
 220         const unsigned char *ip = in;
 221         unsigned char *op = out;
 222         size_t l = in_len;
 223         size_t t = 0;
 224
 225         while (l > 20) {
 226                 size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);
 227                 uintptr_t ll_end = (uintptr_t) ip + ll;
 228                 if ((ll_end + ((t + ll) >> 5)) <= ll_end)
 229                         break;
 230                 BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
 231                 memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
 232                 t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem);
 233                 ip += ll;
 234                 op += *out_len;
 235                 l  -= ll;
 236         }
 237         t += l;
 238
 239         if (t > 0) {
 240                 const unsigned char *ii = in + in_len - t;
 241
 242                 if (op == out && t <= 238) {
 243                         *op++ = (17 + t);
 244                 } else if (t <= 3) {
 245                         op[-2] |= t;
 246                 } else if (t <= 18) {
 247                         *op++ = (t - 3);
 248                 } else {
 249                         size_t tt = t - 18;
 250                         *op++ = 0;
 251                         while (tt > 255) {
 252                                 tt -= 255;
 253                                 *op++ = 0;
 254                         }
 255                         *op++ = tt;
 256                 }
 257                 if (t >= 16) do {
 258                         COPY8(op, ii);
 259                         COPY8(op + 8, ii + 8);
 260                         op += 16;
 261                         ii += 16;
 262                         t -= 16;
 263                 } while (t >= 16);
 264                 if (t > 0) do {
 265                         *op++ = *ii++;
 266                 } while (--t > 0);
 267         }
 268
 269         *op++ = M4_MARKER | 1;
 270         *op++ = 0;
 271         *op++ = 0;
 272
 273         *out_len = op - out;
 274         return LZO_E_OK;
 275 }
 276 EXPORT_SYMBOL_GPL(lzo1x_1_compress);
 277
 278 MODULE_LICENSE("GPL");
 279 MODULE_DESCRIPTION("LZO1X-1 Compressor");