VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/checksum/crc32.cpp@ 67124

Last change on this file since 67124 was 62477, checked in by vboxsync, 8 years ago

(C) 2016

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