git.sesse.net Git - ffmpeg/blob - libavutil/crc.c

   1 /*
   2  * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
   3  *
   4  * This file is part of Libav.
   5  *
   6  * Libav is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * Libav is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with Libav; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include "config.h"
  22 #include "common.h"
  23 #include "bswap.h"
  24 #include "crc.h"
  25
  26 #if CONFIG_HARDCODED_TABLES
  27 #include "crc_data.h"
  28 #else
  29 static struct {
  30     uint8_t  le;
  31     uint8_t  bits;
  32     uint32_t poly;
  33 } av_crc_table_params[AV_CRC_MAX] = {
  34     [AV_CRC_8_ATM]      = { 0,  8,       0x07 },
  35     [AV_CRC_16_ANSI]    = { 0, 16,     0x8005 },
  36     [AV_CRC_16_CCITT]   = { 0, 16,     0x1021 },
  37     [AV_CRC_32_IEEE]    = { 0, 32, 0x04C11DB7 },
  38     [AV_CRC_32_IEEE_LE] = { 1, 32, 0xEDB88320 },
  39 };
  40 static AVCRC av_crc_table[AV_CRC_MAX][257];
  41 #endif
  42
  43 /**
  44  * Initialize a CRC table.
  45  * @param ctx must be an array of size sizeof(AVCRC)*257 or sizeof(AVCRC)*1024
  46  * @param le If 1, the lowest bit represents the coefficient for the highest
  47  *           exponent of the corresponding polynomial (both for poly and
  48  *           actual CRC).
  49  *           If 0, you must swap the CRC parameter and the result of av_crc
  50  *           if you need the standard representation (can be simplified in
  51  *           most cases to e.g. bswap16):
  52  *           av_bswap32(crc << (32-bits))
  53  * @param bits number of bits for the CRC
  54  * @param poly generator polynomial without the x**bits coefficient, in the
  55  *             representation as specified by le
  56  * @param ctx_size size of ctx in bytes
  57  * @return <0 on failure
  58  */
  59 int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size)
  60 {
  61     unsigned i, j;
  62     uint32_t c;
  63
  64     if (bits < 8 || bits > 32 || poly >= (1LL << bits))
  65         return -1;
  66     if (ctx_size != sizeof(AVCRC) * 257 && ctx_size != sizeof(AVCRC) * 1024)
  67         return -1;
  68
  69     for (i = 0; i < 256; i++) {
  70         if (le) {
  71             for (c = i, j = 0; j < 8; j++)
  72                 c = (c >> 1) ^ (poly & (-(c & 1)));
  73             ctx[i] = c;
  74         } else {
  75             for (c = i << 24, j = 0; j < 8; j++)
  76                 c = (c << 1) ^ ((poly << (32 - bits)) & (((int32_t) c) >> 31));
  77             ctx[i] = av_bswap32(c);
  78         }
  79     }
  80     ctx[256] = 1;
  81 #if !CONFIG_SMALL
  82     if (ctx_size >= sizeof(AVCRC) * 1024)
  83         for (i = 0; i < 256; i++)
  84             for (j = 0; j < 3; j++)
  85                 ctx[256 *(j + 1) + i] =
  86                     (ctx[256 * j + i] >> 8) ^ ctx[ctx[256 * j + i] & 0xFF];
  87 #endif
  88
  89     return 0;
  90 }
  91
  92 /**
  93  * Get an initialized standard CRC table.
  94  * @param crc_id ID of a standard CRC
  95  * @return a pointer to the CRC table or NULL on failure
  96  */
  97 const AVCRC *av_crc_get_table(AVCRCId crc_id)
  98 {
  99 #if !CONFIG_HARDCODED_TABLES
 100     if (!av_crc_table[crc_id][FF_ARRAY_ELEMS(av_crc_table[crc_id]) - 1])
 101         if (av_crc_init(av_crc_table[crc_id],
 102                         av_crc_table_params[crc_id].le,
 103                         av_crc_table_params[crc_id].bits,
 104                         av_crc_table_params[crc_id].poly,
 105                         sizeof(av_crc_table[crc_id])) < 0)
 106             return NULL;
 107 #endif
 108     return av_crc_table[crc_id];
 109 }
 110
 111 /**
 112  * Calculate the CRC of a block.
 113  * @param crc CRC of previous blocks if any or initial value for CRC
 114  * @return CRC updated with the data from the given block
 115  *
 116  * @see av_crc_init() "le" parameter
 117  */
 118 uint32_t av_crc(const AVCRC *ctx, uint32_t crc,
 119                 const uint8_t *buffer, size_t length)
 120 {
 121     const uint8_t *end = buffer + length;
 122
 123 #if !CONFIG_SMALL
 124     if (!ctx[256]) {
 125         while (((intptr_t) buffer & 3) && buffer < end)
 126             crc = ctx[((uint8_t) crc) ^ *buffer++] ^ (crc >> 8);
 127
 128         while (buffer < end - 3) {
 129             crc ^= av_le2ne32(*(const uint32_t *) buffer); buffer += 4;
 130             crc = ctx[3 * 256 + ( crc        & 0xFF)] ^
 131                   ctx[2 * 256 + ((crc >> 8 ) & 0xFF)] ^
 132                   ctx[1 * 256 + ((crc >> 16) & 0xFF)] ^
 133                   ctx[0 * 256 + ((crc >> 24)       )];
 134         }
 135     }
 136 #endif
 137     while (buffer < end)
 138         crc = ctx[((uint8_t) crc) ^ *buffer++] ^ (crc >> 8);
 139
 140     return crc;
 141 }
 142
 143 #ifdef TEST
 144 #undef printf
 145 int main(void)
 146 {
 147     uint8_t buf[1999];
 148     int i;
 149     int p[4][3] = { { AV_CRC_32_IEEE_LE, 0xEDB88320, 0x3D5CDD04 },
 150                     { AV_CRC_32_IEEE   , 0x04C11DB7, 0xC0F5BAE0 },
 151                     { AV_CRC_16_ANSI   , 0x8005    , 0x1FBB     },
 152                     { AV_CRC_8_ATM     , 0x07      , 0xE3       }
 153     };
 154     const AVCRC *ctx;
 155
 156     for (i = 0; i < sizeof(buf); i++)
 157         buf[i] = i + i * i;
 158
 159     for (i = 0; i < 4; i++) {
 160         ctx = av_crc_get_table(p[i][0]);
 161         printf("crc %08X = %X\n", p[i][1], av_crc(ctx, 0, buf, sizeof(buf)));
 162     }
 163     return 0;
 164 }
 165 #endif