diff options
Diffstat (limited to 'libphobos/src/std/digest/crc.d')
| -rw-r--r-- | libphobos/src/std/digest/crc.d | 705 |
1 files changed, 705 insertions, 0 deletions
diff --git a/libphobos/src/std/digest/crc.d b/libphobos/src/std/digest/crc.d new file mode 100644 index 0000000..c606f4c --- /dev/null +++ b/libphobos/src/std/digest/crc.d @@ -0,0 +1,705 @@ +/** +Cyclic Redundancy Check (32-bit) implementation. + +$(SCRIPT inhibitQuickIndex = 1;) + +$(DIVC quickindex, +$(BOOKTABLE , +$(TR $(TH Category) $(TH Functions) +) +$(TR $(TDNW Template API) $(TD $(MYREF CRC) $(MYREF CRC32) $(MYREF CRC64ECMA) $(MYREF CRC64ISO) +) +) +$(TR $(TDNW OOP API) $(TD $(MYREF CRC32Digest) $(MYREF CRC64ECMADigest) $(MYREF CRC64ISODigest)) +) +$(TR $(TDNW Helpers) $(TD $(MYREF crcHexString) $(MYREF crc32Of) $(MYREF crc64ECMAOf) $(MYREF crc64ISOOf)) +) +) +) + + * + * This module conforms to the APIs defined in $(D std.digest). To understand the + * differences between the template and the OOP API, see $(MREF std, digest). + * + * This module publicly imports $(MREF std, digest) and can be used as a stand-alone + * module. + * + * Note: + * CRCs are usually printed with the MSB first. When using + * $(REF toHexString, std,digest) the result will be in an unexpected + * order. Use $(REF toHexString, std,digest)'s optional order parameter + * to specify decreasing order for the correct result. The $(LREF crcHexString) + * alias can also be used for this purpose. + * + * License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0). + * + * Authors: Pavel "EvilOne" Minayev, Alex Rønne Petersen, Johannes Pfau + * + * References: + * $(LINK2 http://en.wikipedia.org/wiki/Cyclic_redundancy_check, Wikipedia on CRC) + * + * Source: $(PHOBOSSRC std/digest/_crc.d) + * + * Standards: + * Implements the 'common' IEEE CRC32 variant + * (LSB-first order, Initial value uint.max, complement result) + * + * CTFE: + * Digests do not work in CTFE + */ +/* + * Copyright (c) 2001 - 2002 + * Pavel "EvilOne" Minayev + * Copyright (c) 2012 + * Alex Rønne Petersen + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + */ +module std.digest.crc; + +public import std.digest; + +version (unittest) + import std.exception; + + +/// +@safe unittest +{ + //Template API + import std.digest.crc; + + ubyte[4] hash = crc32Of("The quick brown fox jumps over the lazy dog"); + assert(crcHexString(hash) == "414FA339"); + + //Feeding data + ubyte[1024] data; + CRC32 crc; + crc.put(data[]); + crc.start(); //Start again + crc.put(data[]); + hash = crc.finish(); +} + +/// +@safe unittest +{ + //OOP API + import std.digest.crc; + + auto crc = new CRC32Digest(); + ubyte[] hash = crc.digest("The quick brown fox jumps over the lazy dog"); + assert(crcHexString(hash) == "414FA339"); //352441c2 + + //Feeding data + ubyte[1024] data; + crc.put(data[]); + crc.reset(); //Start again + crc.put(data[]); + hash = crc.finish(); +} + +private T[256][8] genTables(T)(T polynomial) +{ + T[256][8] res = void; + + foreach (i; 0 .. 0x100) + { + T crc = i; + foreach (_; 0 .. 8) + crc = (crc >> 1) ^ (-int(crc & 1) & polynomial); + res[0][i] = crc; + } + + foreach (i; 0 .. 0x100) + { + res[1][i] = (res[0][i] >> 8) ^ res[0][res[0][i] & 0xFF]; + res[2][i] = (res[1][i] >> 8) ^ res[0][res[1][i] & 0xFF]; + res[3][i] = (res[2][i] >> 8) ^ res[0][res[2][i] & 0xFF]; + res[4][i] = (res[3][i] >> 8) ^ res[0][res[3][i] & 0xFF]; + res[5][i] = (res[4][i] >> 8) ^ res[0][res[4][i] & 0xFF]; + res[6][i] = (res[5][i] >> 8) ^ res[0][res[5][i] & 0xFF]; + res[7][i] = (res[6][i] >> 8) ^ res[0][res[6][i] & 0xFF]; + } + return res; +} + +@system unittest +{ + auto tables = genTables(0xEDB88320); + assert(tables[0][0] == 0x00000000 && tables[0][$ - 1] == 0x2d02ef8d && tables[7][$ - 1] == 0x264b06e6); +} + +/** + * Template API CRC32 implementation. + * See $(D std.digest) for differences between template and OOP API. + */ +alias CRC32 = CRC!(32, 0xEDB88320); + +/** + * Template API CRC64-ECMA implementation. + * See $(D std.digest.digest) for differences between template and OOP API. + */ +alias CRC64ECMA = CRC!(64, 0xC96C5795D7870F42); + +/** + * Template API CRC64-ISO implementation. + * See $(D std.digest.digest) for differences between template and OOP API. + */ +alias CRC64ISO = CRC!(64, 0xD800000000000000); + +/** + * Generic Template API used for CRC32 and CRC64 implementations. + * + * The N parameter indicate the size of the hash in bits. + * The parameter P specify the polynomial to be used for reduction. + * + * You may want to use the CRC32, CRC65ECMA and CRC64ISO aliases + * for convenience. + * + * See $(D std.digest.digest) for differences between template and OOP API. + */ +struct CRC(uint N, ulong P) if (N == 32 || N == 64) +{ + private: + static if (N == 32) + { + alias T = uint; + } + else + { + alias T = ulong; + } + + static immutable T[256][8] tables = genTables!T(P); + + /** + * Type of the finished CRC hash. + * ubyte[4] if N is 32, ubyte[8] if N is 64. + */ + alias R = ubyte[T.sizeof]; + + // magic initialization constants + T _state = T.max; + + public: + /** + * Use this to feed the digest with data. + * Also implements the $(REF isOutputRange, std,range,primitives) + * interface for $(D ubyte) and $(D const(ubyte)[]). + */ + void put(scope const(ubyte)[] data...) @trusted pure nothrow @nogc + { + T crc = _state; + // process eight bytes at once + while (data.length >= 8) + { + // Use byte-wise reads to support architectures without HW support + // for unaligned reads. This can be optimized by compilers to a single + // 32-bit read if unaligned reads are supported. + // DMD is not able to do this optimization though, so explicitly + // do unaligned reads for DMD's architectures. + version (X86) + enum hasLittleEndianUnalignedReads = true; + else version (X86_64) + enum hasLittleEndianUnalignedReads = true; + else + enum hasLittleEndianUnalignedReads = false; // leave decision to optimizer + static if (hasLittleEndianUnalignedReads) + { + uint one = (cast(uint*) data.ptr)[0]; + uint two = (cast(uint*) data.ptr)[1]; + } + else + { + uint one = (data.ptr[3] << 24 | data.ptr[2] << 16 | data.ptr[1] << 8 | data.ptr[0]); + uint two = (data.ptr[7] << 24 | data.ptr[6] << 16 | data.ptr[5] << 8 | data.ptr[4]); + } + + static if (N == 32) + { + one ^= crc; + } + else + { + one ^= (crc & 0xffffffff); + two ^= (crc >> 32); + } + + crc = + tables[0][two >> 24] ^ + tables[1][(two >> 16) & 0xFF] ^ + tables[2][(two >> 8) & 0xFF] ^ + tables[3][two & 0xFF] ^ + tables[4][one >> 24] ^ + tables[5][(one >> 16) & 0xFF] ^ + tables[6][(one >> 8) & 0xFF] ^ + tables[7][one & 0xFF]; + + data = data[8 .. $]; + } + // remaining 1 to 7 bytes + foreach (d; data) + crc = (crc >> 8) ^ tables[0][(crc & 0xFF) ^ d]; + _state = crc; + } + + /** + * Used to initialize the CRC32 digest. + * + * Note: + * For this CRC32 Digest implementation calling start after default construction + * is not necessary. Calling start is only necessary to reset the Digest. + * + * Generic code which deals with different Digest types should always call start though. + */ + void start() @safe pure nothrow @nogc + { + this = CRC.init; + } + + /** + * Returns the finished CRC hash. This also calls $(LREF start) to + * reset the internal state. + */ + R finish() @safe pure nothrow @nogc + { + auto tmp = peek(); + start(); + return tmp; + } + + /** + * Works like $(D finish) but does not reset the internal state, so it's possible + * to continue putting data into this CRC after a call to peek. + */ + R peek() const @safe pure nothrow @nogc + { + import std.bitmanip : nativeToLittleEndian; + //Complement, LSB first / Little Endian, see http://rosettacode.org/wiki/CRC-32 + return nativeToLittleEndian(~_state); + } +} + +/// +@safe unittest +{ + //Simple example, hashing a string using crc32Of helper function + ubyte[4] hash32 = crc32Of("abc"); + //Let's get a hash string + assert(crcHexString(hash32) == "352441C2"); + // Repeat for CRC64 + ubyte[8] hash64ecma = crc64ECMAOf("abc"); + assert(crcHexString(hash64ecma) == "2CD8094A1A277627"); + ubyte[8] hash64iso = crc64ISOOf("abc"); + assert(crcHexString(hash64iso) == "3776C42000000000"); +} + +/// +@safe unittest +{ + ubyte[1024] data; + //Using the basic API + CRC32 hash32; + CRC64ECMA hash64ecma; + CRC64ISO hash64iso; + //Initialize data here... + hash32.put(data); + ubyte[4] result32 = hash32.finish(); + hash64ecma.put(data); + ubyte[8] result64ecma = hash64ecma.finish(); + hash64iso.put(data); + ubyte[8] result64iso = hash64iso.finish(); +} + +/// +@safe unittest +{ + //Let's use the template features: + //Note: When passing a CRC32 to a function, it must be passed by reference! + void doSomething(T)(ref T hash) + if (isDigest!T) + { + hash.put(cast(ubyte) 0); + } + CRC32 crc32; + crc32.start(); + doSomething(crc32); + assert(crcHexString(crc32.finish()) == "D202EF8D"); + // repeat for CRC64 + CRC64ECMA crc64ecma; + crc64ecma.start(); + doSomething(crc64ecma); + assert(crcHexString(crc64ecma.finish()) == "1FADA17364673F59"); + CRC64ISO crc64iso; + crc64iso.start(); + doSomething(crc64iso); + assert(crcHexString(crc64iso.finish()) == "6F90000000000000"); +} + +@safe unittest +{ + assert(isDigest!CRC32); + assert(isDigest!CRC64ECMA); + assert(isDigest!CRC64ISO); +} + +@system unittest +{ + ubyte[4] digest; + + CRC32 crc; + crc.put(cast(ubyte[])"abcdefghijklmnopqrstuvwxyz"); + assert(crc.peek() == cast(ubyte[]) x"bd50274c"); + crc.start(); + crc.put(cast(ubyte[])""); + assert(crc.finish() == cast(ubyte[]) x"00000000"); + + digest = crc32Of(""); + assert(digest == cast(ubyte[]) x"00000000"); + + //Test vector from http://rosettacode.org/wiki/CRC-32 + assert(crcHexString(crc32Of("The quick brown fox jumps over the lazy dog")) == "414FA339"); + + digest = crc32Of("a"); + assert(digest == cast(ubyte[]) x"43beb7e8"); + + digest = crc32Of("abc"); + assert(digest == cast(ubyte[]) x"c2412435"); + + digest = crc32Of("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"); + assert(digest == cast(ubyte[]) x"5f3f1a17"); + + digest = crc32Of("message digest"); + assert(digest == cast(ubyte[]) x"7f9d1520"); + + digest = crc32Of("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); + assert(digest == cast(ubyte[]) x"d2e6c21f"); + + digest = crc32Of("1234567890123456789012345678901234567890"~ + "1234567890123456789012345678901234567890"); + assert(digest == cast(ubyte[]) x"724aa97c"); + + assert(crcHexString(cast(ubyte[4]) x"c3fcd3d7") == "D7D3FCC3"); +} + +@system unittest +{ + ubyte[8] digest; + + CRC64ECMA crc; + crc.put(cast(ubyte[])"abcdefghijklmnopqrstuvwxyz"); + assert(crc.peek() == cast(ubyte[]) x"2f121b7575789626"); + crc.start(); + crc.put(cast(ubyte[])""); + assert(crc.finish() == cast(ubyte[]) x"0000000000000000"); + digest = crc64ECMAOf(""); + assert(digest == cast(ubyte[]) x"0000000000000000"); + + //Test vector from http://rosettacode.org/wiki/CRC-32 + assert(crcHexString(crc64ECMAOf("The quick brown fox jumps over the lazy dog")) == "5B5EB8C2E54AA1C4"); + + digest = crc64ECMAOf("a"); + assert(digest == cast(ubyte[]) x"052b652e77840233"); + + digest = crc64ECMAOf("abc"); + assert(digest == cast(ubyte[]) x"2776271a4a09d82c"); + + digest = crc64ECMAOf("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"); + assert(digest == cast(ubyte[]) x"4b7cdce3746c449f"); + + digest = crc64ECMAOf("message digest"); + assert(digest == cast(ubyte[]) x"6f9b8a3156c9bc5d"); + + digest = crc64ECMAOf("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); + assert(digest == cast(ubyte[]) x"2656b716e1bf0503"); + + digest = crc64ECMAOf("1234567890123456789012345678901234567890"~ + "1234567890123456789012345678901234567890"); + assert(digest == cast(ubyte[]) x"bd3eb7765d0a22ae"); + + assert(crcHexString(cast(ubyte[8]) x"c3fcd3d7efbeadde") == "DEADBEEFD7D3FCC3"); +} + +@system unittest +{ + ubyte[8] digest; + + CRC64ISO crc; + crc.put(cast(ubyte[])"abcdefghijklmnopqrstuvwxyz"); + assert(crc.peek() == cast(ubyte[]) x"f0494ab780989b42"); + crc.start(); + crc.put(cast(ubyte[])""); + assert(crc.finish() == cast(ubyte[]) x"0000000000000000"); + digest = crc64ISOOf(""); + assert(digest == cast(ubyte[]) x"0000000000000000"); + + //Test vector from http://rosettacode.org/wiki/CRC-32 + assert(crcHexString(crc64ISOOf("The quick brown fox jumps over the lazy dog")) == "4EF14E19F4C6E28E"); + + digest = crc64ISOOf("a"); + assert(digest == cast(ubyte[]) x"0000000000002034"); + + digest = crc64ISOOf("abc"); + assert(digest == cast(ubyte[]) x"0000000020c47637"); + + digest = crc64ISOOf("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"); + assert(digest == cast(ubyte[]) x"5173f717971365e5"); + + digest = crc64ISOOf("message digest"); + assert(digest == cast(ubyte[]) x"a2c355bbc0b93f86"); + + digest = crc64ISOOf("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"); + assert(digest == cast(ubyte[]) x"598B258292E40084"); + + digest = crc64ISOOf("1234567890123456789012345678901234567890"~ + "1234567890123456789012345678901234567890"); + assert(digest == cast(ubyte[]) x"760cd2d3588bf809"); + + assert(crcHexString(cast(ubyte[8]) x"c3fcd3d7efbeadde") == "DEADBEEFD7D3FCC3"); +} + +/** + * This is a convenience alias for $(REF digest, std,digest) using the + * CRC32 implementation. + * + * Params: + * data = $(D InputRange) of $(D ElementType) implicitly convertible to + * $(D ubyte), $(D ubyte[]) or $(D ubyte[num]) or one or more arrays + * of any type. + * + * Returns: + * CRC32 of data + */ +//simple alias doesn't work here, hope this gets inlined... +ubyte[4] crc32Of(T...)(T data) +{ + return digest!(CRC32, T)(data); +} + +/// +@system unittest +{ + ubyte[] data = [4,5,7,25]; + assert(data.crc32Of == [167, 180, 199, 131]); + + import std.utf : byChar; + assert("hello"d.byChar.crc32Of == [134, 166, 16, 54]); + + ubyte[4] hash = "abc".crc32Of(); + assert(hash == digest!CRC32("ab", "c")); + + import std.range : iota; + enum ubyte S = 5, F = 66; + assert(iota(S, F).crc32Of == [59, 140, 234, 154]); +} + +/** + * This is a convenience alias for $(REF digest, std,digest) using the + * CRC64-ECMA implementation. + * + * Params: + * data = $(D InputRange) of $(D ElementType) implicitly convertible to + * $(D ubyte), $(D ubyte[]) or $(D ubyte[num]) or one or more arrays + * of any type. + * + * Returns: + * CRC64-ECMA of data + */ +//simple alias doesn't work here, hope this gets inlined... +ubyte[8] crc64ECMAOf(T...)(T data) +{ + return digest!(CRC64ECMA, T)(data); +} + +/// +@system unittest +{ + ubyte[] data = [4,5,7,25]; + assert(data.crc64ECMAOf == [58, 142, 220, 214, 118, 98, 105, 69]); + + import std.utf : byChar; + assert("hello"d.byChar.crc64ECMAOf == [177, 55, 185, 219, 229, 218, 30, 155]); + + ubyte[8] hash = "abc".crc64ECMAOf(); + assert("abc".crc64ECMAOf == [39, 118, 39, 26, 74, 9, 216, 44]); + assert(hash == digest!CRC64ECMA("ab", "c")); + + import std.range : iota; + enum ubyte S = 5, F = 66; + assert(iota(S, F).crc64ECMAOf == [6, 184, 91, 238, 46, 213, 127, 188]); +} + +/** + * This is a convenience alias for $(REF digest, std,digest,digest) using the + * CRC64-ISO implementation. + * + * Params: + * data = $(D InputRange) of $(D ElementType) implicitly convertible to + * $(D ubyte), $(D ubyte[]) or $(D ubyte[num]) or one or more arrays + * of any type. + * + * Returns: + * CRC64-ISO of data + */ +//simple alias doesn't work here, hope this gets inlined... +ubyte[8] crc64ISOOf(T...)(T data) +{ + return digest!(CRC64ISO, T)(data); +} + +/// +@system unittest +{ + ubyte[] data = [4,5,7,25]; + assert(data.crc64ISOOf == [0, 0, 0, 80, 137, 232, 203, 120]); + + import std.utf : byChar; + assert("hello"d.byChar.crc64ISOOf == [0, 0, 16, 216, 226, 238, 62, 60]); + + ubyte[8] hash = "abc".crc64ISOOf(); + assert("abc".crc64ISOOf == [0, 0, 0, 0, 32, 196, 118, 55]); + assert(hash == digest!CRC64ISO("ab", "c")); + + import std.range : iota; + enum ubyte S = 5, F = 66; + + assert(iota(S, F).crc64ISOOf == [21, 185, 116, 95, 219, 11, 54, 7]); +} + +/** + * producing the usual CRC32 string output. + */ +public alias crcHexString = toHexString!(Order.decreasing); +///ditto +public alias crcHexString = toHexString!(Order.decreasing, 16); + +/** + * OOP API CRC32 implementation. + * See $(D std.digest) for differences between template and OOP API. + * + * This is an alias for $(D $(REF WrapperDigest, std,digest)!CRC32), see + * there for more information. + */ +alias CRC32Digest = WrapperDigest!CRC32; + +/** + * OOP API CRC64-ECMA implementation. + * See $(D std.digest.digest) for differences between template and OOP API. + * + * This is an alias for $(D $(REF WrapperDigest, std,digest,digest)!CRC64ECMA), + * see there for more information. + */ +alias CRC64ECMADigest = WrapperDigest!CRC64ECMA; + +/** + * OOP API CRC64-ISO implementation. + * See $(D std.digest.digest) for differences between template and OOP API. + * + * This is an alias for $(D $(REF WrapperDigest, std,digest,digest)!CRC64ISO), + * see there for more information. + */ +alias CRC64ISODigest = WrapperDigest!CRC64ISO; + +/// +@safe unittest +{ + //Simple example, hashing a string using Digest.digest helper function + auto crc = new CRC32Digest(); + ubyte[] hash = crc.digest("abc"); + //Let's get a hash string + assert(crcHexString(hash) == "352441C2"); +} + +/// +@system unittest +{ + //Let's use the OOP features: + void test(Digest dig) + { + dig.put(cast(ubyte) 0); + } + auto crc = new CRC32Digest(); + test(crc); + + //Let's use a custom buffer: + ubyte[4] buf; + ubyte[] result = crc.finish(buf[]); + assert(crcHexString(result) == "D202EF8D"); +} + +/// +@safe unittest +{ + //Simple example + auto hash = new CRC32Digest(); + hash.put(cast(ubyte) 0); + ubyte[] result = hash.finish(); +} + +/// +@system unittest +{ + //using a supplied buffer + ubyte[4] buf; + auto hash = new CRC32Digest(); + hash.put(cast(ubyte) 0); + ubyte[] result = hash.finish(buf[]); + //The result is now in result (and in buf. If you pass a buffer which is bigger than + //necessary, result will have the correct length, but buf will still have it's original + //length) +} + +@system unittest +{ + import std.range; + + auto crc = new CRC32Digest(); + + crc.put(cast(ubyte[])"abcdefghijklmnopqrstuvwxyz"); + assert(crc.peek() == cast(ubyte[]) x"bd50274c"); + crc.reset(); + crc.put(cast(ubyte[])""); + assert(crc.finish() == cast(ubyte[]) x"00000000"); + + crc.put(cast(ubyte[])"abcdefghijklmnopqrstuvwxyz"); + ubyte[20] result; + auto result2 = crc.finish(result[]); + assert(result[0 .. 4] == result2 && result2 == cast(ubyte[]) x"bd50274c"); + + debug + assertThrown!Error(crc.finish(result[0 .. 3])); + + assert(crc.length == 4); + + assert(crc.digest("") == cast(ubyte[]) x"00000000"); + + assert(crc.digest("a") == cast(ubyte[]) x"43beb7e8"); + + assert(crc.digest("abc") == cast(ubyte[]) x"c2412435"); + + assert(crc.digest("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") + == cast(ubyte[]) x"5f3f1a17"); + + assert(crc.digest("message digest") == cast(ubyte[]) x"7f9d1520"); + + assert(crc.digest("abcdefghijklmnopqrstuvwxyz") + == cast(ubyte[]) x"bd50274c"); + + assert(crc.digest("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") + == cast(ubyte[]) x"d2e6c21f"); + + assert(crc.digest("1234567890123456789012345678901234567890", + "1234567890123456789012345678901234567890") + == cast(ubyte[]) x"724aa97c"); + + ubyte[] onemilliona = new ubyte[1000000]; + onemilliona[] = 'a'; + auto digest = crc32Of(onemilliona); + assert(digest == cast(ubyte[]) x"BCBF25DC"); + + auto oneMillionRange = repeat!ubyte(cast(ubyte)'a', 1000000); + digest = crc32Of(oneMillionRange); + assert(digest == cast(ubyte[]) x"BCBF25DC"); +} |