~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/lzo/lzo1x_compress.c

Version: ~ [ linux-5.3-rc5 ] ~ [ linux-5.2.9 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.67 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.139 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.189 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.189 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.72 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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");
280 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp