source: trunk/src/blosclz.c @ 114

Revision 114, 11.4 KB checked in by faltet, 4 years ago (diff)

Fixes for supporting MINGW compiler.

Line 
1/*********************************************************************
2  Blosc - Blocked Suffling and Compression Library
3
4  Author: Francesc Alted (faltet@pytables.org)
5  Creation date: 2009-05-20
6
7  See LICENSES/BLOSC.txt for details about copyright and rights to use.
8**********************************************************************/
9
10/*********************************************************************
11  The code in this file is heavily based on FastLZ, a lightning-fast
12  lossless compression library.  See LICENSES/FASTLZ.txt for details.
13**********************************************************************/
14
15
16#include <stdlib.h>
17#include <stdio.h>
18#include <string.h>
19#include "blosclz.h"
20
21#if defined(_WIN32) && !defined(__MINGW32__)
22  #include <windows.h>
23  #include "stdint-windows.h"
24#else
25  #include <stdint.h>
26#endif  /* _WIN32 */
27
28
29/*
30 * Prevent accessing more than 8-bit at once, except on x86 architectures.
31 */
32#if !defined(BLOSCLZ_STRICT_ALIGN)
33#define BLOSCLZ_STRICT_ALIGN
34#if defined(__i386__) || defined(__386) || defined (__amd64)  /* GNU C, Sun Studio */
35#undef BLOSCLZ_STRICT_ALIGN
36#elif defined(__i486__) || defined(__i586__) || defined(__i686__)  /* GNU C */
37#undef BLOSCLZ_STRICT_ALIGN
38#elif defined(_M_IX86) /* Intel, MSVC */
39#undef BLOSCLZ_STRICT_ALIGN
40#elif defined(__386)
41#undef BLOSCLZ_STRICT_ALIGN
42#elif defined(_X86_) /* MinGW */
43#undef BLOSCLZ_STRICT_ALIGN
44#elif defined(__I86__) /* Digital Mars */
45#undef BLOSCLZ_STRICT_ALIGN
46#endif
47#endif
48
49/*
50 * Always check for bound when decompressing.
51 * Generally it is best to leave it defined.
52 */
53#define BLOSCLZ_SAFE
54
55/*
56 * Give hints to the compiler for branch prediction optimization.
57 */
58#if defined(__GNUC__) && (__GNUC__ > 2)
59#define BLOSCLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
60#define BLOSCLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
61#else
62#define BLOSCLZ_EXPECT_CONDITIONAL(c)    (c)
63#define BLOSCLZ_UNEXPECT_CONDITIONAL(c)  (c)
64#endif
65
66/*
67 * Use inlined functions for supported systems.
68 */
69#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
70#define BLOSCLZ_INLINE inline
71#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
72#define BLOSCLZ_INLINE __inline
73#else
74#define BLOSCLZ_INLINE
75#endif
76
77#define MAX_COPY       32
78#define MAX_LEN       264  /* 256 + 8 */
79#define MAX_DISTANCE 8191
80#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
81
82#ifdef BLOSCLZ_STRICT_ALIGN
83  #define BLOSCLZ_READU16(p) ((p)[0] | (p)[1]<<8)
84#else
85  #define BLOSCLZ_READU16(p) *((const uint16_t*)(p))
86#endif
87
88
89BLOSCLZ_INLINE size_t hash_function(uint8_t* p, uint8_t hash_log)
90{
91  size_t v;
92
93  v = BLOSCLZ_READU16(p);
94  v ^= BLOSCLZ_READU16(p+1)^(v>>(16-hash_log));
95  v &= (1 << hash_log) - 1;
96  return v;
97}
98
99
100#define IP_BOUNDARY 2
101
102int blosclz_compress(int opt_level, const void* input,
103                     int length, void* output, int maxout)
104{
105  uint8_t* ip = (uint8_t*) input;
106  uint8_t* ibase = (uint8_t*) input;
107  uint8_t* ip_bound = ip + length - IP_BOUNDARY;
108  uint8_t* ip_limit = ip + length - 12;
109  uint8_t* op = (uint8_t*) output;
110
111  /* Hash table depends on the opt level.  Hash_log cannot be larger than 15. */
112  uint8_t hash_log_[10] = {-1, 8, 9, 9, 11, 11, 11, 12, 12, 13};
113  uint8_t hash_log = hash_log_[opt_level];
114  uint16_t hash_size = 1 << hash_log;
115  uint16_t *htab;
116  uint8_t* op_limit;
117
118  size_t hslot;
119  size_t hval;
120  size_t copy;
121
122  float maxlength_[10] = {-1, .1, .15, .2, .5, .7, .85, .925, .975, 1.0};
123  size_t maxlength = (size_t) (length * maxlength_[opt_level]);
124  if (maxlength > (size_t) maxout) {
125    maxlength = (size_t) maxout;
126  }
127  op_limit = op + maxlength;
128
129  /* output buffer cannot be less than 66 bytes or we can get into problems.
130     As output is usually the same length than input, we take input length. */
131  if (length < 66) {
132    return 0;                   /* Mark this as uncompressible */
133  }
134
135  htab = malloc(hash_size*sizeof(uint16_t));
136
137  /* sanity check */
138  if(BLOSCLZ_UNEXPECT_CONDITIONAL(length < 4)) {
139    if(length) {
140      /* create literal copy only */
141      *op++ = length-1;
142      ip_bound++;
143      while(ip <= ip_bound)
144        *op++ = *ip++;
145      free(htab);
146      return length+1;
147    }
148    else
149      free(htab);
150      return 0;
151  }
152
153  /* initializes hash table */
154  for (hslot = 0; hslot < hash_size; hslot++)
155    htab[hslot] = 0;
156
157  /* we start with literal copy */
158  copy = 2;
159  *op++ = MAX_COPY-1;
160  *op++ = *ip++;
161  *op++ = *ip++;
162
163  /* main loop */
164  while(BLOSCLZ_EXPECT_CONDITIONAL(ip < ip_limit)) {
165    const uint8_t* ref;
166    size_t distance;
167    size_t len = 3;         /* minimum match length */
168    uint8_t* anchor = ip;  /* comparison starting-point */
169
170    /* check for a run */
171    if(ip[0] == ip[-1] && BLOSCLZ_READU16(ip-1)==BLOSCLZ_READU16(ip+1)) {
172      distance = 1;
173      ip += 3;
174      ref = anchor - 1 + 3;
175      goto match;
176    }
177
178    /* find potential match */
179    hval = hash_function(ip, hash_log);
180    ref = ibase + htab[hval];
181    /* update hash table */
182    htab[hval] = anchor - ibase;
183
184    /* calculate distance to the match */
185    distance = anchor - ref;
186
187    /* is this a match? check the first 3 bytes */
188    if (distance==0 || (distance >= MAX_FARDISTANCE) ||
189        *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
190      goto literal;
191
192    /* far, needs at least 5-byte match */
193    if (distance >= MAX_DISTANCE) {
194      if (*ip++ != *ref++ || *ip++ != *ref++)
195        goto literal;
196      len += 2;
197    }
198
199    match:
200
201    /* last matched byte */
202    ip = anchor + len;
203
204    /* distance is biased */
205    distance--;
206
207    if(!distance) {
208      /* zero distance means a run */
209      uint8_t x = ip[-1];
210      int64_t value, value2;
211      /* Broadcast the value for every byte in a 64-bit register */
212      memset(&value, x, 8);
213      /* safe because the outer check against ip limit */
214      while (ip < (ip_bound - (sizeof(int64_t) - IP_BOUNDARY))) {
215        value2 = ((int64_t *)ref)[0];
216        if (value != value2) {
217          /* Find the byte that starts to differ */
218          while (ip < ip_bound) {
219            if (*ref++ != x) break; else ip++;
220          }
221          break;
222        }
223        else {
224          ip += 8;
225          ref += 8;
226        }
227      }
228      if (ip > ip_bound) {
229        long l = ip - ip_bound;
230        ip -= l;
231        ref -= l;
232      }   /* End of optimization */
233    }
234    else {
235      for(;;) {
236        /* safe because the outer check against ip limit */
237        while (ip < (ip_bound - (sizeof(int64_t) - IP_BOUNDARY))) {
238          if (*ref++ != *ip++) break;
239          if (((int64_t *)ref)[0] != ((int64_t *)ip)[0]) {
240            /* Find the byte that starts to differ */
241            while (ip < ip_bound) {
242              if (*ref++ != *ip++) break;
243            }
244            break;
245          }
246          else {
247            ip += 8;
248            ref += 8;
249          }
250        }
251        /* Last correction before exiting loop */
252        if (ip > ip_bound) {
253          size_t l = ip - ip_bound;
254          ip -= l;
255          ref -= l;
256        }   /* End of optimization */
257        break;
258      }
259    }
260
261    /* if we have copied something, adjust the copy count */
262    if (copy)
263      /* copy is biased, '0' means 1 byte copy */
264      *(op-copy-1) = copy-1;
265    else
266      /* back, to overwrite the copy count */
267      op--;
268
269    /* reset literal counter */
270    copy = 0;
271
272    /* length is biased, '1' means a match of 3 bytes */
273    ip -= 3;
274    len = ip - anchor;
275
276    /* encode the match */
277    if(distance < MAX_DISTANCE) {
278      if(len < 7) {
279        *op++ = (len << 5) + (distance >> 8);
280        *op++ = (distance & 255);
281      }
282      else {
283        *op++ = (7 << 5) + (distance >> 8);
284        for(len-=7; len >= 255; len-= 255)
285          *op++ = 255;
286        *op++ = len;
287        *op++ = (distance & 255);
288      }
289    }
290    else {
291      /* far away, but not yet in the another galaxy... */
292      if(len < 7) {
293        distance -= MAX_DISTANCE;
294        *op++ = (len << 5) + 31;
295        *op++ = 255;
296        *op++ = distance >> 8;
297        *op++ = distance & 255;
298      }
299      else {
300        distance -= MAX_DISTANCE;
301        *op++ = (7 << 5) + 31;
302        for(len-=7; len >= 255; len-= 255)
303          *op++ = 255;
304        *op++ = len;
305        *op++ = 255;
306        *op++ = distance >> 8;
307        *op++ = distance & 255;
308      }
309    }
310
311    /* update the hash at match boundary */
312    hval = hash_function(ip, hash_log);
313    htab[hval] = ip++ - ibase;
314    hval = hash_function(ip, hash_log);
315    htab[hval] = ip++ - ibase;
316
317    /* assuming literal copy */
318    *op++ = MAX_COPY-1;
319
320    continue;
321
322    literal:
323      *op++ = *anchor++;
324      ip = anchor;
325      copy++;
326      if(BLOSCLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY)) {
327        copy = 0;
328        *op++ = MAX_COPY-1;
329      }
330      if (op > op_limit) {
331        free(htab);
332        return 0;
333      }
334  }
335
336  /* left-over as literal copy */
337  ip_bound++;
338  while(ip <= ip_bound) {
339    if (op > op_limit) {
340      free(htab);
341      return 0;
342    }
343    *op++ = *ip++;
344    copy++;
345    if(copy == MAX_COPY) {
346      copy = 0;
347      *op++ = MAX_COPY-1;
348    }
349  }
350
351  /* if we have copied something, adjust the copy length */
352  if(copy)
353    *(op-copy-1) = copy-1;
354  else
355    op--;
356
357  /* marker for blosclz */
358  *(uint8_t*)output |= (1 << 5);
359
360  free(htab);
361  return op - (uint8_t*)output;
362}
363
364
365int blosclz_decompress(const void* input, int length, void* output, int maxout)
366{
367  const uint8_t* ip = (const uint8_t*) input;
368  const uint8_t* ip_limit  = ip + length;
369  uint8_t* op = (uint8_t*) output;
370  uint8_t* op_limit = op + maxout;
371  uint32_t ctrl = (*ip++) & 31;
372  size_t loop = 1;
373
374  do {
375    const uint8_t* ref = op;
376    size_t len = ctrl >> 5;
377    size_t ofs = (ctrl & 31) << 8;
378
379    if(ctrl >= 32) {
380      uint8_t code;
381      len--;
382      ref -= ofs;
383      if (len == 7-1)
384        do {
385          code = *ip++;
386          len += code;
387        } while (code==255);
388      code = *ip++;
389      ref -= code;
390
391      /* match from 16-bit distance */
392      if(BLOSCLZ_UNEXPECT_CONDITIONAL(code==255))
393      if(BLOSCLZ_EXPECT_CONDITIONAL(ofs==(31 << 8))) {
394        ofs = (*ip++) << 8;
395        ofs += *ip++;
396        ref = op - ofs - MAX_DISTANCE;
397      }
398
399#ifdef BLOSCLZ_SAFE
400      if (BLOSCLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit)) {
401        return 0;
402      }
403
404      if (BLOSCLZ_UNEXPECT_CONDITIONAL(ref-1 < (uint8_t *)output)) {
405        return 0;
406      }
407#endif
408
409      if(BLOSCLZ_EXPECT_CONDITIONAL(ip < ip_limit))
410        ctrl = *ip++;
411      else
412        loop = 0;
413
414      if(ref == op) {
415        /* optimize copy for a run */
416        uint8_t b = ref[-1];
417        memset(op, b, len+3);
418        op += len+3;
419      }
420      else {
421        /* copy from reference */
422        ref--;
423        len += 3;
424        if (abs(ref-op) <= (int)len) {
425          /* src and dst do overlap: do a loop */
426          for(; len; --len)
427            *op++ = *ref++;
428          /* The memmove below does not work well (don't know why) */
429          /* memmove(op, ref, len);
430             op += len;
431             ref += len;
432             len = 0; */
433        }
434        else {
435          memcpy(op, ref, len);
436          op += len;
437          ref += len;
438        }
439      }
440    }
441    else {
442      ctrl++;
443#ifdef BLOSCLZ_SAFE
444      if (BLOSCLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit)) {
445        return 0;
446      }
447      if (BLOSCLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit)) {
448        return 0;
449      }
450#endif
451
452      memcpy(op, ip, ctrl);
453      ip += ctrl;
454      op += ctrl;
455
456      loop = BLOSCLZ_EXPECT_CONDITIONAL(ip < ip_limit);
457      if(loop)
458        ctrl = *ip++;
459    }
460  } while(BLOSCLZ_EXPECT_CONDITIONAL(loop));
461
462  return op - (uint8_t*)output;
463}
Note: See TracBrowser for help on using the repository browser.