Imported Upstream version 2.08upstream/2.08sandbox/kevinthierry/upstream

1 files changed, 139 insertions, 144 deletions

diff --git a/src/lzo_swd.ch b/src/lzo_swd.ch
index aa4b17c..ea9f931 100644
--- a/src/lzo_swd.ch
+++ b/src/lzo_swd.ch
@@ -2,19 +2,7 @@
 
    This file is part of the LZO real-time data compression library.
 
-   Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
-   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
+   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
    All Rights Reserved.
 
    The LZO library is free software; you can redistribute it and/or
@@ -41,34 +29,27 @@
 #if (LZO_UINT_MAX < LZO_0xffffffffL)
 #  error "LZO_UINT_MAX"
 #endif
+#if defined(LZO_DEBUG)
+#  include <stdio.h>
+#endif
+#if defined(__LZO_CHECKER)
+#  include <stdlib.h>
+#endif
 
 
 /***********************************************************************
 //
 ************************************************************************/
 
-#ifndef SWD_N
-#  define SWD_N             N
-#endif
-#ifndef SWD_F
-#  define SWD_F             F
-#endif
-#ifndef SWD_THRESHOLD
-#  define SWD_THRESHOLD     THRESHOLD
-#endif
-
 /* unsigned type for dictionary access - don't waste memory here */
-#if (0UL + SWD_N + SWD_F + SWD_F < 0UL + USHRT_MAX)
-   typedef unsigned short   swd_uint;
-#  define SWD_UINT_MAX      USHRT_MAX
-#elif (0UL + SWD_N + SWD_F + SWD_F < 0UL + UINT_MAX)
-   typedef unsigned         swd_uint;
-#  define SWD_UINT_MAX      UINT_MAX
+#if (0UL + SWD_N + SWD_F + SWD_F < 65535UL)
+   typedef lzo_uint16_t     swd_uint;
+#  define SWD_UINT_MAX      0xffffu
 #else
-   typedef lzo_uint         swd_uint;
-#  define SWD_UINT_MAX      LZO_UINT_MAX
+   typedef lzo_uint32_t     swd_uint;
+#  define SWD_UINT_MAX      0xffffffffu
 #endif
-#define swd_uintp           swd_uint __LZO_MMODEL *
+#define swd_uintp           swd_uint *
 #define SWD_UINT(x)         ((swd_uint)(x))
 
 
@@ -89,22 +70,25 @@
 #endif
 #endif
 
-#if (SWD_THRESHOLD == 1) && !defined(HEAD2)
-#  if 1 && defined(LZO_UNALIGNED_OK_2)
-#    define HEAD2(b,p)      (* (lzo_ushortp) &(b[p]))
+#if !(SWD_NO_HEAD2) && (SWD_THRESHOLD == 1) && !defined(HEAD2)
+#  if 1 && (LZO_OPT_UNALIGNED16)
+#    define HEAD2(b,p)      UA_GET_NE16((b)+(p))
 #  else
-#    define HEAD2(b,p)      (b[p] ^ ((unsigned)b[p+1]<<8))
+#    define HEAD2(b,p)      (b[p] ^ ((unsigned)b[(p)+1]<<8))
 #  endif
 #  define NIL2              SWD_UINT_MAX
 #endif
+#ifndef IF_HEAD2
+#define IF_HEAD2(s)         /*empty*/
+#endif
 
 
 typedef struct
 {
 /* public - "built-in" */
-    lzo_uint n;
-    lzo_uint f;
-    lzo_uint threshold;
+    lzo_uint swd_n;
+    lzo_uint swd_f;
+    lzo_uint swd_threshold;
 
 /* public - configuration */
     lzo_uint max_chain;
@@ -144,32 +128,7 @@ typedef struct
     lzo_uint node_count;
     lzo_uint first_rp;
 
-#if defined(__LZO_MMODEL_HUGE)
-#  define A(type, n)    ((((n) * sizeof(type)) + 3UL) &~ 3UL)
-
-#  define O_b(s)        (0L)
-#  define O_head3(s)    (O_b(s) + A(char, 0UL + SWD_N + SWD_F + SWD_F))
-#  define O_succ3(s)    (O_head3(s) + A(swd_uint, 0UL + SWD_HSIZE))
-#  define O_best3(s)    (O_succ3(s) + A(swd_uint, 0UL + SWD_N + SWD_F))
-#  define O_llen3(s)    (O_best3(s) + A(swd_uint, 0UL + SWD_N + SWD_F))
-# ifdef HEAD2
-#  define O_head2(s)    (O_llen3(s) + A(swd_uint, 0UL + SWD_HSIZE))
-#  define O_END(s)      (O_head2(s) + A(swd_uint, 0UL + 65536L))
-# else
-#  define O_END(s)      (O_llen3(s) + A(swd_uint, 0UL + SWD_HSIZE))
-# endif
-
-#  define S_DEF(s,type,off)  ((type) ((lzo_bytep)s + 0L + sizeof(*s) + off))
-#  define s_b(s)        S_DEF(s, lzo_bytep, O_b(s))
-#  define s_head3(s)    S_DEF(s, swd_uintp, O_head3(s))
-#  define s_succ3(s)    S_DEF(s, swd_uintp, O_succ3(s))
-#  define s_best3(s)    S_DEF(s, swd_uintp, O_best3(s))
-#  define s_llen3(s)    S_DEF(s, swd_uintp, O_llen3(s))
-# ifdef HEAD2
-#  define s_head2(s)    S_DEF(s, swd_uintp, O_head2(s))
-# endif
-
-#elif defined(__LZO_CHECKER)
+#if defined(__LZO_CHECKER)
     /* malloc arrays of the exact size to detect any overrun */
     unsigned char *b;
     swd_uint *head3;
@@ -192,12 +151,9 @@ typedef struct
 #endif
 }
 lzo_swd_t;
-#define lzo_swd_p   lzo_swd_t __LZO_MMODEL *
+#define lzo_swd_p   lzo_swd_t *
 
 
-#if defined(__LZO_MMODEL_HUGE)
-#define SIZEOF_LZO_SWD_T    O_END(0)
-#else
 #define s_b(s)      s->b
 #define s_head3(s)  s->head3
 #define s_succ3(s)  s->succ3
@@ -207,17 +163,17 @@ lzo_swd_t;
 #define s_head2(s)  s->head2
 #endif
 #define SIZEOF_LZO_SWD_T    (sizeof(lzo_swd_t))
-#endif
 
 
 /* Access macro for head3.
- * head3[key] may be uninitialized, but then its value will never be used.
+ * head3[key] may be uninitialized if the list is emtpy,
+ * but then its value will never be used.
  */
-#if defined(__LZO_CHECKER)
+#if 1 || defined(__LZO_CHECKER)
 #  define s_get_head3(s,key) \
-        ((s->llen3[key] == 0) ? SWD_UINT_MAX : s_head3(s)[key])
+        ((swd_uint)((s_llen3(s)[key] == 0) ? SWD_UINT_MAX : s_head3(s)[key]))
 #else
-#  define s_get_head3(s,key)    s_head3(s)[key]
+#  define s_get_head3(s,key)    (s_head3(s)[key])
 #endif
 
 
@@ -231,12 +187,12 @@ void swd_initdict(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len)
     s->dict = s->dict_end = NULL;
     s->dict_len = 0;
 
-    if (!dict || dict_len <= 0)
+    if (!dict || dict_len == 0)
         return;
-    if (dict_len > s->n)
+    if (dict_len > s->swd_n)
     {
-        dict += dict_len - s->n;
-        dict_len = s->n;
+        dict += dict_len - s->swd_n;
+        dict_len = s->swd_n;
     }
 
     s->dict = dict;
@@ -252,25 +208,28 @@ void swd_insertdict(lzo_swd_p s, lzo_uint node, lzo_uint len)
 {
     lzo_uint key;
 
-    s->node_count = s->n - len;
+    s->node_count = s->swd_n - len;
     s->first_rp = node;
 
-    while (len-- > 0)
+    if (len) do
     {
         key = HEAD3(s_b(s),node);
         s_succ3(s)[node] = s_get_head3(s,key);
         s_head3(s)[key] = SWD_UINT(node);
-        s_best3(s)[node] = SWD_UINT(s->f + 1);
+        s_best3(s)[node] = SWD_UINT(s->swd_f + 1);
         s_llen3(s)[key]++;
-        assert(s_llen3(s)[key] <= SWD_N);
+        assert(s_llen3(s)[key] <= s->swd_n);
 
 #ifdef HEAD2
-        key = HEAD2(s_b(s),node);
-        s_head2(s)[key] = SWD_UINT(node);
+        IF_HEAD2(s) {
+            key = HEAD2(s_b(s),node);
+            s_head2(s)[key] = SWD_UINT(node);
+        }
 #endif
 
         node++;
     }
+    while (--len != 0);
 }
 
 
@@ -278,53 +237,78 @@ void swd_insertdict(lzo_swd_p s, lzo_uint node, lzo_uint len)
 //
 ************************************************************************/
 
+static void swd_exit(lzo_swd_p s);
+
 static
 int swd_init(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len)
 {
-    lzo_uint i = 0;
-    int c = 0;
-
 #if defined(__LZO_CHECKER)
-    s->b = malloc(SWD_N + SWD_F + SWD_F);
-    s->head3 = malloc(sizeof(swd_uint) * SWD_HSIZE);
-    s->succ3 = malloc(sizeof(swd_uint) * (SWD_N + SWD_F));
-    s->best3 = malloc(sizeof(swd_uint) * (SWD_N + SWD_F));
-    s->llen3 = malloc(sizeof(swd_uint) * SWD_HSIZE);
+    unsigned r = 1;
+    s->b = (lzo_bytep) malloc(SWD_N + SWD_F + SWD_F);
+    s->head3 = (swd_uintp) malloc(sizeof(swd_uint) * SWD_HSIZE);
+    s->succ3 = (swd_uintp) malloc(sizeof(swd_uint) * (SWD_N + SWD_F));
+    s->best3 = (swd_uintp) malloc(sizeof(swd_uint) * (SWD_N + SWD_F));
+    s->llen3 = (swd_uintp) malloc(sizeof(swd_uint) * SWD_HSIZE);
+    r &= s->b != NULL;
+    r &= s->head3 != NULL;
+    r &= s->succ3 != NULL;
+    r &= s->best3 != NULL;
+    r &= s->llen3 != NULL;
 #ifdef HEAD2
-    s->head2 = malloc(sizeof(swd_uint) * 65536L);
+    IF_HEAD2(s) {
+        s->head2 = (swd_uintp) malloc(sizeof(swd_uint) * 65536L);
+        r &= s->head2 != NULL;
+    }
 #endif
+    if (r != 1) {
+        swd_exit(s);
+        return LZO_E_OUT_OF_MEMORY;
+    }
 #endif
 
-    s->n = SWD_N;
-    s->f = SWD_F;
-    s->threshold = SWD_THRESHOLD;
+    s->m_len = 0;
+    s->m_off = 0;
+#if defined(SWD_BEST_OFF)
+    {
+        unsigned i;
+        for (i = 0; i < SWD_BEST_OFF; i++)
+            s->best_off[i] = s->best_pos[i] = 0;
+    }
+#endif
+
+    s->swd_n = SWD_N;
+    s->swd_f = SWD_F;
+    s->swd_threshold = SWD_THRESHOLD;
 
     /* defaults */
     s->max_chain = SWD_MAX_CHAIN;
-    s->nice_length = SWD_F;
+    s->nice_length = s->swd_f;
     s->use_best_off = 0;
     s->lazy_insert = 0;
 
-    s->b_size = s->n + s->f;
+    s->b_size = s->swd_n + s->swd_f;
 #if 0
-    if (2 * s->f >= s->n || s->b_size + s->f >= SWD_UINT_MAX)
+    if (2 * s->swd_f >= s->swd_n || s->b_size + s->swd_f >= SWD_UINT_MAX)
         return LZO_E_ERROR;
 #else
     LZO_COMPILE_TIME_ASSERT(!(0ul + 2 * SWD_F >= SWD_N))
     LZO_COMPILE_TIME_ASSERT(!(0ul + SWD_N + SWD_F + SWD_F >= SWD_UINT_MAX))
 #endif
     s->b_wrap = s_b(s) + s->b_size;
-    s->node_count = s->n;
+    s->node_count = s->swd_n;
 
-    lzo_memset(s_llen3(s), 0, sizeof(s_llen3(s)[0]) * (lzo_uint)SWD_HSIZE);
+    lzo_memset(s_llen3(s), 0, (lzo_uint)sizeof(s_llen3(s)[0]) * (lzo_uint)SWD_HSIZE);
 #ifdef HEAD2
+    IF_HEAD2(s) {
 #if 1
-    lzo_memset(s_head2(s), 0xff, sizeof(s_head2(s)[0]) * 65536L);
-    assert(s_head2(s)[0] == NIL2);
+        lzo_memset(s_head2(s), 0xff, (lzo_uint)sizeof(s_head2(s)[0]) * 65536L);
+        assert(s_head2(s)[0] == NIL2);
 #else
-    for (i = 0; i < 65536L; i++)
-        s_head2(s)[i] = NIL2;
+        lzo_xint i;
+        for (i = 0; i < 65536L; i++)
+            s_head2(s)[i] = NIL2;
 #endif
+    }
 #endif
 
     s->ip = 0;
@@ -332,21 +316,22 @@ int swd_init(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len)
     s->bp = s->ip;
     s->first_rp = s->ip;
 
-    assert(s->ip + s->f <= s->b_size);
+    assert(s->ip + s->swd_f <= s->b_size);
 #if 1
     s->look = (lzo_uint) (s->c->in_end - s->c->ip);
     if (s->look > 0)
     {
-        if (s->look > s->f)
-            s->look = s->f;
+        if (s->look > s->swd_f)
+            s->look = s->swd_f;
         lzo_memcpy(&s_b(s)[s->ip],s->c->ip,s->look);
         s->c->ip += s->look;
         s->ip += s->look;
     }
 #else
     s->look = 0;
-    while (s->look < s->f)
+    while (s->look < s->swd_f)
     {
+        int c;
         if ((c = getbyte(*(s->c))) < 0)
             break;
         s_b(s)[s->ip] = LZO_BYTE(c);
@@ -366,15 +351,15 @@ int swd_init(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len)
     else
         s->rp += s->b_size - s->node_count;
 
-#if defined(__LZO_CHECKER)
+#if 1 || defined(__LZO_CHECKER)
     /* initialize memory for the first few HEAD3 (if s->ip is not far
      * enough ahead to do this job for us). The value doesn't matter. */
-    if (s->look < 3)
-        lzo_memset(&s_b(s)[s->bp+s->look],0,3);
+    if (s->look < 3) {
+        lzo_bytep p = &s_b(s)[s->bp+s->look];
+        p[0] = p[1] = p[2] = 0;
+    }
 #endif
 
-    LZO_UNUSED(i);
-    LZO_UNUSED(c);
     return LZO_E_OK;
 }
 
@@ -415,17 +400,17 @@ void swd_getbyte(lzo_swd_p s)
     {
         if (s->look > 0)
             --s->look;
-#if defined(__LZO_CHECKER)
+#if 1 || defined(__LZO_CHECKER)
         /* initialize memory - value doesn't matter */
         s_b(s)[s->ip] = 0;
-        if (s->ip < s->f)
+        if (s->ip < s->swd_f)
             s->b_wrap[s->ip] = 0;
 #endif
     }
     else
     {
         s_b(s)[s->ip] = LZO_BYTE(c);
-        if (s->ip < s->f)
+        if (s->ip < s->swd_f)
             s->b_wrap[s->ip] = LZO_BYTE(c);
     }
     if (++s->ip == s->b_size)
@@ -452,9 +437,10 @@ void swd_remove_node(lzo_swd_p s, lzo_uint node)
         if (s->first_rp != LZO_UINT_MAX)
         {
             if (node != s->first_rp)
-                printf("Remove %5u: %5u %5u %5u %5u  %6u %6u\n",
-                        node, s->rp, s->ip, s->bp, s->first_rp,
-                        s->ip - node, s->ip - s->bp);
+                printf("Remove %5ld: %5ld %5ld %5ld %5ld  %6ld %6ld\n",
+                        (long)node, (long)s->rp, (long)s->ip, (long)s->bp,
+                        (long)s->first_rp, (long)(s->ip - node),
+                        (long)(s->ip - s->bp));
             assert(node == s->first_rp);
             s->first_rp = LZO_UINT_MAX;
         }
@@ -465,10 +451,12 @@ void swd_remove_node(lzo_swd_p s, lzo_uint node)
         --s_llen3(s)[key];
 
 #ifdef HEAD2
-        key = HEAD2(s_b(s),node);
-        assert(s_head2(s)[key] != NIL2);
-        if ((lzo_uint) s_head2(s)[key] == node)
-            s_head2(s)[key] = NIL2;
+        IF_HEAD2(s) {
+            key = HEAD2(s_b(s),node);
+            assert(s_head2(s)[key] != NIL2);
+            if ((lzo_uint) s_head2(s)[key] == node)
+                s_head2(s)[key] = NIL2;
+        }
 #endif
     }
     else
@@ -485,7 +473,7 @@ void swd_accept(lzo_swd_p s, lzo_uint n)
 {
     assert(n <= s->look);
 
-    while (n--)
+    if (n) do
     {
         lzo_uint key;
 
@@ -495,18 +483,20 @@ void swd_accept(lzo_swd_p s, lzo_uint n)
         key = HEAD3(s_b(s),s->bp);
         s_succ3(s)[s->bp] = s_get_head3(s,key);
         s_head3(s)[key] = SWD_UINT(s->bp);
-        s_best3(s)[s->bp] = SWD_UINT(s->f + 1);
+        s_best3(s)[s->bp] = SWD_UINT(s->swd_f + 1);
         s_llen3(s)[key]++;
-        assert(s_llen3(s)[key] <= SWD_N);
+        assert(s_llen3(s)[key] <= s->swd_n);
 
 #ifdef HEAD2
         /* add bp into HEAD2 */
-        key = HEAD2(s_b(s),s->bp);
-        s_head2(s)[key] = SWD_UINT(s->bp);
+        IF_HEAD2(s) {
+            key = HEAD2(s_b(s),s->bp);
+            s_head2(s)[key] = SWD_UINT(s->bp);
+        }
 #endif
 
         swd_getbyte(s);
-    }
+    } while (--n != 0);
 }
 
 
@@ -548,9 +538,9 @@ void swd_search(lzo_swd_p s, lzo_uint node, lzo_uint cnt)
             lzo_uint i;
             assert(lzo_memcmp(bp,&b[node],3) == 0);
 
-#if 0 && defined(LZO_UNALIGNED_OK_4)
+#if 0 && (LZO_OPT_UNALIGNED32)
             p1 += 3; p2 += 3;
-            while (p1 < px && * (const lzo_uint32p) p1 == * (const lzo_uint32p) p2)
+            while (p1 + 4 <= px && UA_GET_NE32(p1) == UA_GET_NE32(p2))
                 p1 += 4, p2 += 4;
             while (p1 < px && *p1 == *p2)
                 p1 += 1, p2 += 1;
@@ -562,8 +552,8 @@ void swd_search(lzo_swd_p s, lzo_uint node, lzo_uint cnt)
 
 #ifdef LZO_DEBUG
             if (lzo_memcmp(bp,&b[node],i) != 0)
-                printf("%5ld %5ld %02x%02x %02x%02x\n",
-                        (long)s->bp, (long) node,
+                printf("%5ld %5ld %5ld %02x/%02x %02x/%02x\n",
+                        (long)s->bp, (long) node, (long) i,
                         bp[0], bp[1], b[node], b[node+1]);
 #endif
             assert(lzo_memcmp(bp,&b[node],i) == 0);
@@ -611,7 +601,7 @@ lzo_bool swd_search2(lzo_swd_p s)
         return 0;
 #ifdef LZO_DEBUG
     if (lzo_memcmp(&s_b(s)[s->bp],&s_b(s)[key],2) != 0)
-        printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key,
+        printf("%5ld %5ld %02x/%02x %02x/%02x\n", (long)s->bp, (long)key,
                 s_b(s)[s->bp], s_b(s)[s->bp+1], s_b(s)[key], s_b(s)[key+1]);
 #endif
     assert(lzo_memcmp(&s_b(s)[s->bp],&s_b(s)[key],2) == 0);
@@ -648,7 +638,7 @@ void swd_findbest(lzo_swd_p s)
     key = HEAD3(s_b(s),s->bp);
     node = s_succ3(s)[s->bp] = s_get_head3(s,key);
     cnt = s_llen3(s)[key]++;
-    assert(s_llen3(s)[key] <= SWD_N + SWD_F);
+    assert(s_llen3(s)[key] <= s->swd_n + s->swd_f);
     if (cnt > s->max_chain && s->max_chain > 0)
         cnt = s->max_chain;
     s_head3(s)[key] = SWD_UINT(s->bp);
@@ -660,15 +650,17 @@ void swd_findbest(lzo_swd_p s)
         if (s->look == 0)
             s->b_char = -1;
         s->m_off = 0;
-        s_best3(s)[s->bp] = SWD_UINT(s->f + 1);
+        s_best3(s)[s->bp] = SWD_UINT(s->swd_f + 1);
     }
     else
     {
-#ifdef HEAD2
-        if (swd_search2(s))
+#if defined(HEAD2)
+        if (swd_search2(s) && s->look >= 3)
+            swd_search(s,node,cnt);
+#else
+        if (s->look >= 3)
+            swd_search(s,node,cnt);
 #endif
-            if (s->look >= 3)
-                swd_search(s,node,cnt);
         if (s->m_len > len)
             s->m_off = swd_pos2off(s,s->m_pos);
         s_best3(s)[s->bp] = SWD_UINT(s->m_len);
@@ -676,7 +668,7 @@ void swd_findbest(lzo_swd_p s)
 #if defined(SWD_BEST_OFF)
         if (s->use_best_off)
         {
-            int i;
+            unsigned i;
             for (i = 2; i < SWD_BEST_OFF; i++)
                 if (s->best_pos[i] > 0)
                     s->best_off[i] = swd_pos2off(s,s->best_pos[i]-1);
@@ -690,14 +682,17 @@ void swd_findbest(lzo_swd_p s)
 
 #ifdef HEAD2
     /* add bp into HEAD2 */
-    key = HEAD2(s_b(s),s->bp);
-    s_head2(s)[key] = SWD_UINT(s->bp);
+    IF_HEAD2(s) {
+        key = HEAD2(s_b(s),s->bp);
+        s_head2(s)[key] = SWD_UINT(s->bp);
+    }
 #endif
 }
 
 
 #undef HEAD3
 #undef HEAD2
+#undef IF_HEAD2
 #undef s_get_head3