VirtualBox

source: vbox/trunk/src/VBox/Runtime/crc32.cpp@ 5229

Last change on this file since 5229 was 4071, checked in by vboxsync, 17 years ago

Biggest check-in ever. New source code headers for all (C) innotek files.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 7.8 KB
Line 
1/* $Id: crc32.cpp 4071 2007-08-07 17:07:59Z vboxsync $ */
2/** @file
3 * innotek Portable Runtime - CRC32.
4 */
5
6/*
7 * Copyright (C) 2006-2007 innotek GmbH
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License as published by the Free Software Foundation,
13 * in version 2 as it comes in the "COPYING" file of the VirtualBox OSE
14 * distribution. VirtualBox OSE is distributed in the hope that it will
15 * be useful, but WITHOUT ANY WARRANTY of any kind.
16 * --------------------------------------------------------------------
17 *
18 * This code is based on:
19 *
20 * CRC32 code derived from work by Gary S. Brown.
21 *
22 * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or
23 * code or tables extracted from it, as desired without restriction.
24 *
25 * First, the polynomial itself and its table of feedback terms. The
26 * polynomial is
27 * 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+X^0
28 *
29 * Note that we take it "backwards" and put the highest-order term in
30 * the lowest-order bit. The X^32 term is "implied"; the LSB is the
31 * X^31 term, etc. The X^0 term (usually shown as "+1") results in
32 * the MSB being 1
33 *
34 * Note that the usual hardware shift register implementation, which
35 * is what we're using (we're merely optimizing it by doing eight-bit
36 * chunks at a time) shifts bits into the lowest-order term. In our
37 * implementation, that means shifting towards the right. Why do we
38 * do it this way? Because the calculated CRC must be transmitted in
39 * order from highest-order term to lowest-order term. UARTs transmit
40 * characters in order from LSB to MSB. By storing the CRC this way
41 * we hand it to the UART in the order low-byte to high-byte; the UART
42 * sends each low-bit to hight-bit; and the result is transmission bit
43 * by bit from highest- to lowest-order term without requiring any bit
44 * shuffling on our part. Reception works similarly
45 *
46 * The feedback terms table consists of 256, 32-bit entries. Notes
47 *
48 * The table can be generated at runtime if desired; code to do so
49 * is shown later. It might not be obvious, but the feedback
50 * terms simply represent the results of eight shift/xor opera
51 * tions for all combinations of data and CRC register values
52 *
53 * The values must be right-shifted by eight bits by the "updcrc
54 * logic; the shift must be unsigned (bring in zeroes). On some
55 * hardware you could probably optimize the shift in assembler by
56 * using byte-swap instructions
57 * polynomial $edb88320
58 *
59 */
60
61#if 0
62#include <sys/cdefs.h>
63__FBSDID("$FreeBSD: src/sys/libkern/crc32.c,v 1.2 2003/06/11 05:23:04 obrien Exp $");
64
65#include <sys/param.h>
66#include <sys/systm.h>
67#else
68# include <iprt/crc32.h>
69#endif
70
71#if 0
72uint32_t crc32_tab[] = {
73#else
74/** CRC32 feedback table. */
75uint32_t au32CRC32[] =
76{
77#endif
78 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
79 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
80 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
81 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
82 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
83 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
84 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
85 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
86 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
87 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
88 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
89 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
90 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
91 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
92 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
93 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
94 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
95 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
96 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
97 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
98 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
99 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
100 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
101 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
102 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
103 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
104 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
105 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
106 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
107 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
108 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
109 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
110 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
111 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
112 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
113 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
114 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
115 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
116 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
117 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
118 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
119 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
120 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
121};
122
123#if 0
124uint32_t
125crc32(const void *buf, size_t size)
126{
127 const uint8_t *p;
128 uint32_t crc;
129
130 p = buf;
131 crc = ~0U;
132
133 while (size--)
134 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
135
136 return crc ^ ~0U;
137}
138#endif
139
140
141
142
143/**
144 * Calculate CRC32 for a memory block.
145 *
146 * @returns CRC32 for the memory block.
147 * @param pv Pointer to the memory block.
148 * @param cb Size of the memory block in bytes.
149 */
150RTDECL(uint32_t) RTCrc32(const void *pv, size_t cb)
151{
152 const uint8_t *pu8 = (const uint8_t *)pv;
153 uint32_t uCRC32 = ~0U;
154 while (cb--)
155 uCRC32 = au32CRC32[(uCRC32 ^ *pu8++) & 0xff] ^ (uCRC32 >> 8);
156 return uCRC32 ^ ~0U;
157}
158
159
160/**
161 * Start a multiblock CRC32 calculation.
162 *
163 * @returns Start CRC32.
164 */
165RTDECL(uint32_t) RTCrc32Start(void)
166{
167 return ~0U;
168}
169
170
171/**
172 * Processes a multiblock of a CRC32 calculation.
173 *
174 * @returns Intermediate CRC32 value.
175 * @param uCRC32 Current CRC32 intermediate value.
176 * @param pv The data block to process.
177 * @param cb The size of the data block in bytes.
178 */
179RTDECL(uint32_t) RTCrc32Process(uint32_t uCRC32, const void *pv, size_t cb)
180{
181 const uint8_t *pu8 = (const uint8_t *)pv;
182 while (cb--)
183 uCRC32 = au32CRC32[(uCRC32 ^ *pu8++) & 0xff] ^ (uCRC32 >> 8);
184 return uCRC32;
185}
186
187
188/**
189 * Complete a multiblock CRC32 calculation.
190 *
191 * @returns CRC32 value.
192 * @param uCRC32 Current CRC32 intermediate value.
193 */
194RTDECL(uint32_t) RTCrc32Finish(uint32_t uCRC32)
195{
196 return uCRC32 ^ ~0U;
197}
198
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette