VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/checksum/crc64.cpp@ 81106

Last change on this file since 81106 was 76553, checked in by vboxsync, 6 years ago

scm --update-copyright-year

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
  • Property syn:sync-process set to export
File size: 10.6 KB
Line 
1/* $Id: crc64.cpp 76553 2019-01-01 01:45:53Z vboxsync $ */
2/** @file
3 * IPRT - CRC64.
4 *
5 * The method to compute the CRC64 is referred to as CRC-64-ISO:
6 * http://en.wikipedia.org/wiki/Cyclic_redundancy_check
7 * The generator polynomial is x^64 + x^4 + x^3 + x + 1.
8 * Reverse polynom: 0xd800000000000000ULL
9 */
10
11/*
12 * Copyright (C) 2006-2019 Oracle Corporation
13 *
14 * This file is part of VirtualBox Open Source Edition (OSE), as
15 * available from http://www.virtualbox.org. This file is free software;
16 * you can redistribute it and/or modify it under the terms of the GNU
17 * General Public License (GPL) as published by the Free Software
18 * Foundation, in version 2 as it comes in the "COPYING" file of the
19 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
20 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
21 *
22 * The contents of this file may alternatively be used under the terms
23 * of the Common Development and Distribution License Version 1.0
24 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
25 * VirtualBox OSE distribution, in which case the provisions of the
26 * CDDL are applicable instead of those of the GPL.
27 *
28 * You may elect to license modified versions of this file under the
29 * terms and conditions of either the GPL or the CDDL or both.
30 */
31
32
33/*********************************************************************************************************************************
34* Header Files *
35*********************************************************************************************************************************/
36#include <iprt/crc.h>
37#include "internal/iprt.h"
38
39
40/*********************************************************************************************************************************
41* Global Variables *
42*********************************************************************************************************************************/
43/**
44 * Lookup table (precomputed CRC64 values for each 8 bit string) computation
45 * takes into account the fact that the reverse polynom has zeros in lower 8 bits:
46 *
47 * @code
48 * for (i = 0; i < 256; i++)
49 * {
50 * shiftRegister = i;
51 * for (j = 0; j < 8; j++)
52 * {
53 * if (shiftRegister & 1)
54 * shiftRegister = (shiftRegister >> 1) ^ Reverse_polynom;
55 * else
56 * shiftRegister >>= 1;
57 * }
58 * CRCTable[i] = shiftRegister;
59 * }
60 * @endcode
61 *
62 * Generic code would look as follows:
63 *
64 * @code
65 * for (i = 0; i < 256; i++)
66 * {
67 * shiftRegister = 0;
68 * bitString = i;
69 * for (j = 0; j < 8; j++)
70 * {
71 * if ((shiftRegister ^ (bitString >> j)) & 1)
72 * shiftRegister = (shiftRegister >> 1) ^ Reverse_polynom;
73 * else
74 * shiftRegister >>= 1;
75 * }
76 * CRCTable[i] = shiftRegister;
77 * }
78 * @endcode
79 *
80 * @remark Since the lookup table elements have 0 in the lower 32 bit word,
81 * the 32 bit assembler implementation of CRC64Process can be optimized,
82 * avoiding at least one 'xor' operation.
83 */
84static const uint64_t g_au64CRC64[] =
85{
86 0x0000000000000000ULL, 0x01B0000000000000ULL, 0x0360000000000000ULL, 0x02D0000000000000ULL,
87 0x06C0000000000000ULL, 0x0770000000000000ULL, 0x05A0000000000000ULL, 0x0410000000000000ULL,
88 0x0D80000000000000ULL, 0x0C30000000000000ULL, 0x0EE0000000000000ULL, 0x0F50000000000000ULL,
89 0x0B40000000000000ULL, 0x0AF0000000000000ULL, 0x0820000000000000ULL, 0x0990000000000000ULL,
90 0x1B00000000000000ULL, 0x1AB0000000000000ULL, 0x1860000000000000ULL, 0x19D0000000000000ULL,
91 0x1DC0000000000000ULL, 0x1C70000000000000ULL, 0x1EA0000000000000ULL, 0x1F10000000000000ULL,
92 0x1680000000000000ULL, 0x1730000000000000ULL, 0x15E0000000000000ULL, 0x1450000000000000ULL,
93 0x1040000000000000ULL, 0x11F0000000000000ULL, 0x1320000000000000ULL, 0x1290000000000000ULL,
94 0x3600000000000000ULL, 0x37B0000000000000ULL, 0x3560000000000000ULL, 0x34D0000000000000ULL,
95 0x30C0000000000000ULL, 0x3170000000000000ULL, 0x33A0000000000000ULL, 0x3210000000000000ULL,
96 0x3B80000000000000ULL, 0x3A30000000000000ULL, 0x38E0000000000000ULL, 0x3950000000000000ULL,
97 0x3D40000000000000ULL, 0x3CF0000000000000ULL, 0x3E20000000000000ULL, 0x3F90000000000000ULL,
98 0x2D00000000000000ULL, 0x2CB0000000000000ULL, 0x2E60000000000000ULL, 0x2FD0000000000000ULL,
99 0x2BC0000000000000ULL, 0x2A70000000000000ULL, 0x28A0000000000000ULL, 0x2910000000000000ULL,
100 0x2080000000000000ULL, 0x2130000000000000ULL, 0x23E0000000000000ULL, 0x2250000000000000ULL,
101 0x2640000000000000ULL, 0x27F0000000000000ULL, 0x2520000000000000ULL, 0x2490000000000000ULL,
102 0x6C00000000000000ULL, 0x6DB0000000000000ULL, 0x6F60000000000000ULL, 0x6ED0000000000000ULL,
103 0x6AC0000000000000ULL, 0x6B70000000000000ULL, 0x69A0000000000000ULL, 0x6810000000000000ULL,
104 0x6180000000000000ULL, 0x6030000000000000ULL, 0x62E0000000000000ULL, 0x6350000000000000ULL,
105 0x6740000000000000ULL, 0x66F0000000000000ULL, 0x6420000000000000ULL, 0x6590000000000000ULL,
106 0x7700000000000000ULL, 0x76B0000000000000ULL, 0x7460000000000000ULL, 0x75D0000000000000ULL,
107 0x71C0000000000000ULL, 0x7070000000000000ULL, 0x72A0000000000000ULL, 0x7310000000000000ULL,
108 0x7A80000000000000ULL, 0x7B30000000000000ULL, 0x79E0000000000000ULL, 0x7850000000000000ULL,
109 0x7C40000000000000ULL, 0x7DF0000000000000ULL, 0x7F20000000000000ULL, 0x7E90000000000000ULL,
110 0x5A00000000000000ULL, 0x5BB0000000000000ULL, 0x5960000000000000ULL, 0x58D0000000000000ULL,
111 0x5CC0000000000000ULL, 0x5D70000000000000ULL, 0x5FA0000000000000ULL, 0x5E10000000000000ULL,
112 0x5780000000000000ULL, 0x5630000000000000ULL, 0x54E0000000000000ULL, 0x5550000000000000ULL,
113 0x5140000000000000ULL, 0x50F0000000000000ULL, 0x5220000000000000ULL, 0x5390000000000000ULL,
114 0x4100000000000000ULL, 0x40B0000000000000ULL, 0x4260000000000000ULL, 0x43D0000000000000ULL,
115 0x47C0000000000000ULL, 0x4670000000000000ULL, 0x44A0000000000000ULL, 0x4510000000000000ULL,
116 0x4C80000000000000ULL, 0x4D30000000000000ULL, 0x4FE0000000000000ULL, 0x4E50000000000000ULL,
117 0x4A40000000000000ULL, 0x4BF0000000000000ULL, 0x4920000000000000ULL, 0x4890000000000000ULL,
118 0xD800000000000000ULL, 0xD9B0000000000000ULL, 0xDB60000000000000ULL, 0xDAD0000000000000ULL,
119 0xDEC0000000000000ULL, 0xDF70000000000000ULL, 0xDDA0000000000000ULL, 0xDC10000000000000ULL,
120 0xD580000000000000ULL, 0xD430000000000000ULL, 0xD6E0000000000000ULL, 0xD750000000000000ULL,
121 0xD340000000000000ULL, 0xD2F0000000000000ULL, 0xD020000000000000ULL, 0xD190000000000000ULL,
122 0xC300000000000000ULL, 0xC2B0000000000000ULL, 0xC060000000000000ULL, 0xC1D0000000000000ULL,
123 0xC5C0000000000000ULL, 0xC470000000000000ULL, 0xC6A0000000000000ULL, 0xC710000000000000ULL,
124 0xCE80000000000000ULL, 0xCF30000000000000ULL, 0xCDE0000000000000ULL, 0xCC50000000000000ULL,
125 0xC840000000000000ULL, 0xC9F0000000000000ULL, 0xCB20000000000000ULL, 0xCA90000000000000ULL,
126 0xEE00000000000000ULL, 0xEFB0000000000000ULL, 0xED60000000000000ULL, 0xECD0000000000000ULL,
127 0xE8C0000000000000ULL, 0xE970000000000000ULL, 0xEBA0000000000000ULL, 0xEA10000000000000ULL,
128 0xE380000000000000ULL, 0xE230000000000000ULL, 0xE0E0000000000000ULL, 0xE150000000000000ULL,
129 0xE540000000000000ULL, 0xE4F0000000000000ULL, 0xE620000000000000ULL, 0xE790000000000000ULL,
130 0xF500000000000000ULL, 0xF4B0000000000000ULL, 0xF660000000000000ULL, 0xF7D0000000000000ULL,
131 0xF3C0000000000000ULL, 0xF270000000000000ULL, 0xF0A0000000000000ULL, 0xF110000000000000ULL,
132 0xF880000000000000ULL, 0xF930000000000000ULL, 0xFBE0000000000000ULL, 0xFA50000000000000ULL,
133 0xFE40000000000000ULL, 0xFFF0000000000000ULL, 0xFD20000000000000ULL, 0xFC90000000000000ULL,
134 0xB400000000000000ULL, 0xB5B0000000000000ULL, 0xB760000000000000ULL, 0xB6D0000000000000ULL,
135 0xB2C0000000000000ULL, 0xB370000000000000ULL, 0xB1A0000000000000ULL, 0xB010000000000000ULL,
136 0xB980000000000000ULL, 0xB830000000000000ULL, 0xBAE0000000000000ULL, 0xBB50000000000000ULL,
137 0xBF40000000000000ULL, 0xBEF0000000000000ULL, 0xBC20000000000000ULL, 0xBD90000000000000ULL,
138 0xAF00000000000000ULL, 0xAEB0000000000000ULL, 0xAC60000000000000ULL, 0xADD0000000000000ULL,
139 0xA9C0000000000000ULL, 0xA870000000000000ULL, 0xAAA0000000000000ULL, 0xAB10000000000000ULL,
140 0xA280000000000000ULL, 0xA330000000000000ULL, 0xA1E0000000000000ULL, 0xA050000000000000ULL,
141 0xA440000000000000ULL, 0xA5F0000000000000ULL, 0xA720000000000000ULL, 0xA690000000000000ULL,
142 0x8200000000000000ULL, 0x83B0000000000000ULL, 0x8160000000000000ULL, 0x80D0000000000000ULL,
143 0x84C0000000000000ULL, 0x8570000000000000ULL, 0x87A0000000000000ULL, 0x8610000000000000ULL,
144 0x8F80000000000000ULL, 0x8E30000000000000ULL, 0x8CE0000000000000ULL, 0x8D50000000000000ULL,
145 0x8940000000000000ULL, 0x88F0000000000000ULL, 0x8A20000000000000ULL, 0x8B90000000000000ULL,
146 0x9900000000000000ULL, 0x98B0000000000000ULL, 0x9A60000000000000ULL, 0x9BD0000000000000ULL,
147 0x9FC0000000000000ULL, 0x9E70000000000000ULL, 0x9CA0000000000000ULL, 0x9D10000000000000ULL,
148 0x9480000000000000ULL, 0x9530000000000000ULL, 0x97E0000000000000ULL, 0x9650000000000000ULL,
149 0x9240000000000000ULL, 0x93F0000000000000ULL, 0x9120000000000000ULL, 0x9090000000000000ULL
150};
151
152
153/**
154 * Calculate CRC64 for a memory block.
155 *
156 * @returns CRC64 for the memory block.
157 * @param pv Pointer to the memory block.
158 * @param cb Size of the memory block in bytes.
159 */
160RTDECL(uint64_t) RTCrc64(const void *pv, size_t cb)
161{
162 const uint8_t *pu8 = (const uint8_t *)pv;
163 uint64_t uCRC64 = 0ULL;
164 while (cb--)
165 uCRC64 = g_au64CRC64[(uCRC64 ^ *pu8++) & 0xff] ^ (uCRC64 >> 8);
166 return uCRC64;
167}
168RT_EXPORT_SYMBOL(RTCrc64);
169
170
171/**
172 * Start a multiblock CRC64 calculation.
173 *
174 * @returns Start CRC64.
175 */
176RTDECL(uint64_t) RTCrc64Start(void)
177{
178 return 0ULL;
179}
180RT_EXPORT_SYMBOL(RTCrc64Start);
181
182
183/**
184 * Processes a multiblock of a CRC64 calculation.
185 *
186 * @returns Intermediate CRC64 value.
187 * @param uCRC64 Current CRC64 intermediate value.
188 * @param pv The data block to process.
189 * @param cb The size of the data block in bytes.
190 */
191RTDECL(uint64_t) RTCrc64Process(uint64_t uCRC64, const void *pv, size_t cb)
192{
193 const uint8_t *pu8 = (const uint8_t *)pv;
194 while (cb--)
195 uCRC64 = g_au64CRC64[(uCRC64 ^ *pu8++) & 0xff] ^ (uCRC64 >> 8);
196 return uCRC64;
197}
198RT_EXPORT_SYMBOL(RTCrc64Process);
199
200
201/**
202 * Complete a multiblock CRC64 calculation.
203 *
204 * @returns CRC64 value.
205 * @param uCRC64 Current CRC64 intermediate value.
206 */
207RTDECL(uint64_t) RTCrc64Finish(uint64_t uCRC64)
208{
209 return uCRC64;
210}
211RT_EXPORT_SYMBOL(RTCrc64Finish);
212
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