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 227