bit.cpp

00001 /*
00002  * libmad - MPEG audio decoder library
00003  * Copyright (C) 2000-2004 Underbit Technologies, Inc.
00004  *
00005  * This program is free software; you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License as published by
00007  * the Free Software Foundation; either version 2 of the License, or
00008  * (at your option) any later version.
00009  *
00010  * This program is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  * GNU General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00018  *
00019  * $Id: bit.c,v 1.1 2010/11/23 20:12:57 andy Exp $
00020  */
00021 
00022 #  include "config.h"
00023 
00024 # include "global.h"
00025 
00026 # ifdef HAVE_LIMITS_H
00027 #  include <limits.h>
00028 # else
00029 #  define CHAR_BIT  8
00030 # endif
00031 
00032 # include "bit.h"
00033 
00034 /*
00035  * This is the lookup table for computing the CRC-check word.
00036  * As described in section 2.4.3.1 and depicted in Figure A.9
00037  * of ISO/IEC 11172-3, the generator polynomial is:
00038  *
00039  * G(X) = X^16 + X^15 + X^2 + 1
00040  */
00041 static
00042 unsigned short const crc_table[256] = {
00043   0x0000, 0x8005, 0x800f, 0x000a, 0x801b, 0x001e, 0x0014, 0x8011,
00044   0x8033, 0x0036, 0x003c, 0x8039, 0x0028, 0x802d, 0x8027, 0x0022,
00045   0x8063, 0x0066, 0x006c, 0x8069, 0x0078, 0x807d, 0x8077, 0x0072,
00046   0x0050, 0x8055, 0x805f, 0x005a, 0x804b, 0x004e, 0x0044, 0x8041,
00047   0x80c3, 0x00c6, 0x00cc, 0x80c9, 0x00d8, 0x80dd, 0x80d7, 0x00d2,
00048   0x00f0, 0x80f5, 0x80ff, 0x00fa, 0x80eb, 0x00ee, 0x00e4, 0x80e1,
00049   0x00a0, 0x80a5, 0x80af, 0x00aa, 0x80bb, 0x00be, 0x00b4, 0x80b1,
00050   0x8093, 0x0096, 0x009c, 0x8099, 0x0088, 0x808d, 0x8087, 0x0082,
00051 
00052   0x8183, 0x0186, 0x018c, 0x8189, 0x0198, 0x819d, 0x8197, 0x0192,
00053   0x01b0, 0x81b5, 0x81bf, 0x01ba, 0x81ab, 0x01ae, 0x01a4, 0x81a1,
00054   0x01e0, 0x81e5, 0x81ef, 0x01ea, 0x81fb, 0x01fe, 0x01f4, 0x81f1,
00055   0x81d3, 0x01d6, 0x01dc, 0x81d9, 0x01c8, 0x81cd, 0x81c7, 0x01c2,
00056   0x0140, 0x8145, 0x814f, 0x014a, 0x815b, 0x015e, 0x0154, 0x8151,
00057   0x8173, 0x0176, 0x017c, 0x8179, 0x0168, 0x816d, 0x8167, 0x0162,
00058   0x8123, 0x0126, 0x012c, 0x8129, 0x0138, 0x813d, 0x8137, 0x0132,
00059   0x0110, 0x8115, 0x811f, 0x011a, 0x810b, 0x010e, 0x0104, 0x8101,
00060 
00061   0x8303, 0x0306, 0x030c, 0x8309, 0x0318, 0x831d, 0x8317, 0x0312,
00062   0x0330, 0x8335, 0x833f, 0x033a, 0x832b, 0x032e, 0x0324, 0x8321,
00063   0x0360, 0x8365, 0x836f, 0x036a, 0x837b, 0x037e, 0x0374, 0x8371,
00064   0x8353, 0x0356, 0x035c, 0x8359, 0x0348, 0x834d, 0x8347, 0x0342,
00065   0x03c0, 0x83c5, 0x83cf, 0x03ca, 0x83db, 0x03de, 0x03d4, 0x83d1,
00066   0x83f3, 0x03f6, 0x03fc, 0x83f9, 0x03e8, 0x83ed, 0x83e7, 0x03e2,
00067   0x83a3, 0x03a6, 0x03ac, 0x83a9, 0x03b8, 0x83bd, 0x83b7, 0x03b2,
00068   0x0390, 0x8395, 0x839f, 0x039a, 0x838b, 0x038e, 0x0384, 0x8381,
00069 
00070   0x0280, 0x8285, 0x828f, 0x028a, 0x829b, 0x029e, 0x0294, 0x8291,
00071   0x82b3, 0x02b6, 0x02bc, 0x82b9, 0x02a8, 0x82ad, 0x82a7, 0x02a2,
00072   0x82e3, 0x02e6, 0x02ec, 0x82e9, 0x02f8, 0x82fd, 0x82f7, 0x02f2,
00073   0x02d0, 0x82d5, 0x82df, 0x02da, 0x82cb, 0x02ce, 0x02c4, 0x82c1,
00074   0x8243, 0x0246, 0x024c, 0x8249, 0x0258, 0x825d, 0x8257, 0x0252,
00075   0x0270, 0x8275, 0x827f, 0x027a, 0x826b, 0x026e, 0x0264, 0x8261,
00076   0x0220, 0x8225, 0x822f, 0x022a, 0x823b, 0x023e, 0x0234, 0x8231,
00077   0x8213, 0x0216, 0x021c, 0x8219, 0x0208, 0x820d, 0x8207, 0x0202
00078 };
00079 
00080 # define CRC_POLY  0x8005
00081 
00082 /*
00083  * NAME:    bit->init()
00084  * DESCRIPTION: initialize bit pointer struct
00085  */
00086 void mad_bit_init(struct mad_bitptr *bitptr, unsigned char const *byte)
00087 {
00088   bitptr->byte  = byte;
00089   bitptr->cache = 0;
00090   bitptr->left  = CHAR_BIT;
00091 }
00092 
00093 /*
00094  * NAME:    bit->length()
00095  * DESCRIPTION: return number of bits between start and end points
00096  */
00097 unsigned int mad_bit_length(struct mad_bitptr const *begin,
00098                 struct mad_bitptr const *end)
00099 {
00100   return begin->left +
00101     CHAR_BIT * (end->byte - (begin->byte + 1)) + (CHAR_BIT - end->left);
00102 }
00103 
00104 /*
00105  * NAME:    bit->nextbyte()
00106  * DESCRIPTION: return pointer to next unprocessed byte
00107  */
00108 unsigned char const *mad_bit_nextbyte(struct mad_bitptr const *bitptr)
00109 {
00110   return bitptr->left == CHAR_BIT ? bitptr->byte : bitptr->byte + 1;
00111 }
00112 
00113 /*
00114  * NAME:    bit->skip()
00115  * DESCRIPTION: advance bit pointer
00116  */
00117 void mad_bit_skip(struct mad_bitptr *bitptr, unsigned int len)
00118 {
00119   bitptr->byte += len / CHAR_BIT;
00120   bitptr->left -= len % CHAR_BIT;
00121 
00122   if (bitptr->left > CHAR_BIT) {
00123     bitptr->byte++;
00124     bitptr->left += CHAR_BIT;
00125   }
00126 
00127   if (bitptr->left < CHAR_BIT)
00128     bitptr->cache = *bitptr->byte;
00129 }
00130 
00131 /*
00132  * NAME:    bit->read()
00133  * DESCRIPTION: read an arbitrary number of bits and return their UIMSBF value
00134  */
00135 unsigned long mad_bit_read(struct mad_bitptr *bitptr, unsigned int len)
00136 {
00137   register unsigned long value;
00138 
00139   if (bitptr->left == CHAR_BIT)
00140     bitptr->cache = *bitptr->byte;
00141 
00142   if (len < bitptr->left) {
00143     value = (bitptr->cache & ((1 << bitptr->left) - 1)) >>
00144       (bitptr->left - len);
00145     bitptr->left -= len;
00146 
00147     return value;
00148   }
00149 
00150   /* remaining bits in current byte */
00151 
00152   value = bitptr->cache & ((1 << bitptr->left) - 1);
00153   len  -= bitptr->left;
00154 
00155   bitptr->byte++;
00156   bitptr->left = CHAR_BIT;
00157 
00158   /* more bytes */
00159 
00160   while (len >= CHAR_BIT) {
00161     value = (value << CHAR_BIT) | *bitptr->byte++;
00162     len  -= CHAR_BIT;
00163   }
00164 
00165   if (len > 0) {
00166     bitptr->cache = *bitptr->byte;
00167 
00168     value = (value << len) | (bitptr->cache >> (CHAR_BIT - len));
00169     bitptr->left -= len;
00170   }
00171 
00172   return value;
00173 }
00174 
00175 # if 0
00176 /*
00177  * NAME:    bit->write()
00178  * DESCRIPTION: write an arbitrary number of bits
00179  */
00180 void mad_bit_write(struct mad_bitptr *bitptr, unsigned int len,
00181            unsigned long value)
00182 {
00183   unsigned char *ptr;
00184 
00185   ptr = (unsigned char *) bitptr->byte;
00186 
00187   /* ... */
00188 }
00189 # endif
00190 
00191 /*
00192  * NAME:    bit->crc()
00193  * DESCRIPTION: compute CRC-check word
00194  */
00195 unsigned short mad_bit_crc(struct mad_bitptr bitptr, unsigned int len,
00196                unsigned short init)
00197 {
00198   register unsigned int crc;
00199 
00200   for (crc = init; len >= 32; len -= 32) {
00201     register unsigned long data;
00202 
00203     data = mad_bit_read(&bitptr, 32);
00204 
00205     crc = (crc << 8) ^ crc_table[((crc >> 8) ^ (data >> 24)) & 0xff];
00206     crc = (crc << 8) ^ crc_table[((crc >> 8) ^ (data >> 16)) & 0xff];
00207     crc = (crc << 8) ^ crc_table[((crc >> 8) ^ (data >>  8)) & 0xff];
00208     crc = (crc << 8) ^ crc_table[((crc >> 8) ^ (data >>  0)) & 0xff];
00209   }
00210 
00211   switch (len / 8) {
00212   case 3: crc = (crc << 8) ^
00213         crc_table[((crc >> 8) ^ mad_bit_read(&bitptr, 8)) & 0xff];
00214   case 2: crc = (crc << 8) ^
00215         crc_table[((crc >> 8) ^ mad_bit_read(&bitptr, 8)) & 0xff];
00216   case 1: crc = (crc << 8) ^
00217         crc_table[((crc >> 8) ^ mad_bit_read(&bitptr, 8)) & 0xff];
00218 
00219   len %= 8;
00220 
00221   case 0: break;
00222   }
00223 
00224   while (len--) {
00225     register unsigned int msb;
00226 
00227     msb = mad_bit_read(&bitptr, 1) ^ (crc >> 15);
00228 
00229     crc <<= 1;
00230     if (msb & 1)
00231       crc ^= CRC_POLY;
00232   }
00233 
00234   return crc & 0xffff;
00235 }