utils/Install/packzip/crctab.c

   1 /* crctab.c -- supply the CRC table needed for CRC-32 calculations.
   2  * Copyright (C) 1995 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  */
   5
   6 /* $Id$ */
   7
   8 /*
   9   Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
  10   x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
  11
  12   Polynomials over GF(2) are represented in binary, one bit per coefficient,
  13   with the lowest powers in the most significant bit.  Then adding polynomials
  14   is just exclusive-or, and multiplying a polynomial by x is a right shift by
  15   one.  If we call the above polynomial p, and represent a byte as the
  16   polynomial q, also with the lowest power in the most significant bit (so the
  17   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  18   where a mod b means the remainder after dividing a by b.
  19
  20   This calculation is done using the shift-register method of multiplying and
  21   taking the remainder.  The register is initialized to zero, and for each
  22   incoming bit, x^32 is added mod p to the register if the bit is a one (where
  23   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  24   x (which is shifting right by one and adding x^32 mod p if the bit shifted
  25   out is a one).  We start with the highest power (least significant bit) of
  26   q and repeat for all eight bits of q.
  27
  28   The table is simply the CRC of all possible eight bit values.  This is all
  29   the information needed to generate CRC's on data a byte at a time for all
  30   combinations of CRC register values and incoming bytes.
  31 */
  32
  33 #define __CRCTAB_C      /* identifies this source module */
  34
  35 #include "zip.h"
  36
  37 #if (!defined(USE_ZLIB) || defined(USE_OWN_CRCTAB))
  38
  39 #ifndef ZCONST
  40 #  define ZCONST const
  41 #endif
  42
  43 #ifdef DYNAMIC_CRC_TABLE
  44
  45 /* =========================================================================
  46  * Make the crc table. This function is needed only if you want to compute
  47  * the table dynamically.
  48  */
  49
  50 local void make_crc_table OF((void));
  51
  52 #if (defined(DYNALLOC_CRCTAB) && defined(REENTRANT))
  53    error: Dynamic allocation of CRC table not safe with reentrant code.
  54 #endif /* DYNALLOC_CRCTAB && REENTRANT */
  55
  56 #ifdef DYNALLOC_CRCTAB
  57    local ulg near *crc_table = NULL;
  58 # if 0          /* not used, since sizeof("near *") <= sizeof(int) */
  59    /* Use this section when access to a "local int" is faster than access to
  60       a "local pointer" (e.g.: i86 16bit code with far pointers). */
  61    local int crc_table_empty = 1;
  62 #  define CRC_TABLE_IS_EMPTY    (crc_table_empty != 0)
  63 #  define MARK_CRCTAB_FILLED    crc_table_empty = 0
  64 #  define MARK_CRCTAB_EMPTY     crc_table_empty = 1
  65 # else
  66    /* Use this section on systems where the size of pointers and ints is
  67       equal (e.g.: all 32bit systems). */
  68 #  define CRC_TABLE_IS_EMPTY    (crc_table == NULL)
  69 #  define MARK_CRCTAB_FILLED    crc_table = crctab_p
  70 #  define MARK_CRCTAB_EMPTY     crc_table = NULL
  71 # endif
  72 #else /* !DYNALLOC_CRCTAB */
  73    local ulg near crc_table[256];
  74    local int crc_table_empty = 1;
  75 #  define CRC_TABLE_IS_EMPTY    (crc_table_empty != 0)
  76 #  define MARK_CRCTAB_FILLED    crc_table_empty = 0
  77 #endif /* ?DYNALLOC_CRCTAB */
  78
  79
  80 local void make_crc_table()
  81 {
  82   ulg c;                /* crc shift register */
  83   int n;                /* counter for all possible eight bit values */
  84   int k;                /* byte being shifted into crc apparatus */
  85 #ifdef DYNALLOC_CRCTAB
  86   ulg near *crctab_p;   /* temporary pointer to allocated crc_table area */
  87 #else /* !DYNALLOC_CRCTAB */
  88 # define crctab_p crc_table
  89 #endif /* DYNALLOC_CRCTAB */
  90
  91 #ifdef COMPUTE_XOR_PATTERN
  92   /* This piece of code has been left here to explain how the XOR pattern
  93    * used in the creation of the crc_table values can be recomputed.
  94    * For production versions of this function, it is more efficient to
  95    * supply the resultant pattern at compile time.
  96    */
  97   ulg xor;              /* polynomial exclusive-or pattern */
  98   /* terms of polynomial defining this crc (except x^32): */
  99   static uch p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
 100
 101   /* make exclusive-or pattern from polynomial (0xedb88320L) */
 102   xor = 0L;
 103   for (i = 0; i < sizeof(p)/sizeof(uch); i++)
 104     xor |= 1L << (31 - p[i]);
 105 #else
 106 # define xor 0xedb88320L
 107 #endif
 108
 109 #ifdef DYNALLOC_CRCTAB
 110   crctab_p = (ulg near *) nearmalloc (256*sizeof(ulg));
 111   if (crctab_p == NULL) {
 112     ziperr(ZE_MEM, "crc_table allocation");
 113   }
 114 #endif /* DYNALLOC_CRCTAB */
 115
 116   for (n = 0; n < 256; n++) {
 117     c = (ulg)n;
 118     for (k = 8; k; k--)
 119       c = c & 1 ? xor ^ (c >> 1) : c >> 1;
 120     crctab_p[n] = c;
 121   }
 122   MARK_CRCTAB_FILLED;
 123 }
 124
 125 #else /* !DYNAMIC_CRC_TABLE */
 126
 127 #ifdef DYNALLOC_CRCTAB
 128    error: Inconsistent flags, DYNALLOC_CRCTAB without DYNAMIC_CRC_TABLE.
 129 #endif
 130
 131 /* ========================================================================
 132  * Table of CRC-32's of all single-byte values (made by make_crc_table)
 133  */
 134 local ZCONST ulg near crc_table[256] = {
 135   0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
 136   0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
 137   0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
 138   0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
 139   0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
 140   0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
 141   0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
 142   0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
 143   0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
 144   0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
 145   0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
 146   0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
 147   0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
 148   0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
 149   0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
 150   0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
 151   0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
 152   0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
 153   0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
 154   0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
 155   0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
 156   0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
 157   0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
 158   0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
 159   0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
 160   0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
 161   0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
 162   0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
 163   0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
 164   0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
 165   0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
 166   0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
 167   0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
 168   0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
 169   0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
 170   0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
 171   0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
 172   0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
 173   0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
 174   0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
 175   0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
 176   0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
 177   0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
 178   0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
 179   0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
 180   0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
 181   0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
 182   0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
 183   0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
 184   0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
 185   0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
 186   0x2d02ef8dL
 187 };
 188 #endif /* ?DYNAMIC_CRC_TABLE */
 189
 190 /* use "OF((void))" here to work around a Borland TC++ 1.0 problem */
 191 #ifdef USE_ZLIB
 192 ZCONST uLongf *get_crc_table OF((void))
 193 #else
 194 ZCONST ulg near *get_crc_table OF((void))
 195 #endif
 196 {
 197 #ifdef DYNAMIC_CRC_TABLE
 198   if (CRC_TABLE_IS_EMPTY)
 199     make_crc_table();
 200 #endif
 201 #ifdef USE_ZLIB
 202   return (ZCONST uLongf *)crc_table;
 203 #else
 204   return (ZCONST ulg near *)crc_table;
 205 #endif
 206 }
 207
 208 #ifdef DYNALLOC_CRCTAB
 209 void free_crc_table()
 210 {
 211   if (!CRC_TABLE_IS_EMPTY)
 212   {
 213     nearfree((ulg near *)crc_table);
 214     MARK_CRCTAB_EMPTY;
 215   }
 216 }
 217 #endif
 218
 219 #endif /* !USE_ZLIB || USE_OWN_CRCTAB */