1 /******************************************************************************* 2 3 Variadic-sized value type to represent a hash 4 5 A `BitBlob` is a value type representing a hash. 6 The argument is the size in bits, e.g. for sha256 it is 256. 7 It can be initialized from the hexadecimal string representation 8 or an `ubyte[]`, making it easy to interact with `std.digest` 9 10 Author: Mathias 'Geod24' Lang 11 License: MIT (See LICENSE.txt) 12 Copyright: Copyright (c) 2017-2018 Mathias Lang. All rights reserved. 13 14 *******************************************************************************/ 15 16 module geod24.bitblob; 17 18 static import std.ascii; 19 import std.algorithm.iteration : each, map; 20 import std.algorithm.searching : countUntil, startsWith; 21 import std.format; 22 import std.range; 23 import std.utf; 24 25 /// 26 @nogc @safe pure nothrow unittest 27 { 28 /// Alias for a 256 bits / 32 byte hash type 29 alias Hash = BitBlob!32; 30 31 import std.digest.sha; 32 // Can be initialized from an `ubyte[32]` 33 // (or `ubyte[]` of length 32) 34 Hash fromSha = sha256Of("Hello World"); 35 36 // Of from a string 37 Hash genesis = GenesisBlockHashStr; 38 39 assert(!genesis.isNull()); 40 assert(Hash.init.isNull()); 41 42 ubyte[5] empty; 43 assert(Hash.init < genesis); 44 // The underlying 32 bytes can be access through `opIndex` and `opSlice` 45 assert(genesis[$ - 5 .. $] == empty); 46 } 47 48 49 /******************************************************************************* 50 51 A value type representing a large binary value 52 53 Params: 54 Size = The size of the hash, in bytes 55 56 *******************************************************************************/ 57 58 public struct BitBlob (size_t Size) 59 { 60 @safe: 61 62 /// Convenience enum 63 public enum StringBufferSize = (Size * 2 + 2); 64 65 /*************************************************************************** 66 67 Format the hash as a lowercase hex string 68 69 Used by `std.format` and other formatting primitives. 70 Does not allocate/throw if the sink does not allocate/throw. 71 72 See_Also: 73 https://issues.dlang.org/show_bug.cgi?id=21722 74 75 Params: 76 sink = A delegate that can be called repeatedly to accumulate the data 77 spec = The format spec to be used for the hex string representation. 78 's' (which is default) - 0x prefix and lowercase hex 79 'X' : uppercase hex 80 'x' : lowercase hex 81 82 83 ***************************************************************************/ 84 85 public void toString (scope void delegate(const(char)[]) @safe sink) const 86 { 87 FormatSpec!char spec; 88 this.toString(sink, spec); 89 } 90 91 /// Ditto 92 public void toString (scope void delegate(const(char)[]) @safe sink, 93 scope const ref FormatSpec!char spec) const 94 { 95 /// Used for formatting 96 static immutable LHexDigits = `0123456789abcdef`; 97 static immutable HHexDigits = `0123456789ABCDEF`; 98 99 void formatDigits (immutable string hex_digits) 100 { 101 char[2] data; 102 // retro because the data is stored in little endian 103 this.data[].retro.each!( 104 (bin) 105 { 106 data[0] = hex_digits[bin >> 4]; 107 data[1] = hex_digits[(bin & 0b0000_1111)]; 108 sink(data); 109 }); 110 } 111 112 switch (spec.spec) 113 { 114 case 'X': 115 formatDigits(HHexDigits); 116 break; 117 case 's': 118 default: 119 sink("0x"); 120 goto case; 121 case 'x': 122 formatDigits(LHexDigits); 123 break; 124 } 125 } 126 127 /*************************************************************************** 128 129 Get the string representation of this hash 130 131 Only performs one allocation. 132 133 ***************************************************************************/ 134 135 public string toString () const 136 { 137 size_t idx; 138 char[StringBufferSize] buffer = void; 139 scope sink = (const(char)[] v) { 140 buffer[idx .. idx + v.length] = v; 141 idx += v.length; 142 }; 143 this.toString(sink); 144 return buffer.idup; 145 } 146 147 /*************************************************************************** 148 149 Support deserialization 150 151 Vibe.d expects the `toString`/`fromString` to be present for it to 152 correctly serialize and deserialize a type. 153 This allows to use this type as parameter in `vibe.web.rest` methods, 154 or use it with Vibe.d's serialization module. 155 This function does more extensive validation of the input than the 156 constructor and can be given user input. 157 158 ***************************************************************************/ 159 160 static auto fromString (scope const(char)[] str) 161 { 162 // Ignore prefix 163 if (str.startsWith("0x") || str.startsWith("0X")) 164 str = str[2 .. $]; 165 166 // Then check length 167 if (str.length != Size * 2) 168 throw new Exception( 169 format("Cannot parse string '%s' of length %s: Expected %s chars (%s with prefix)", 170 str, str.length, Size * 2, Size * 2 + 2)); 171 172 // Then content check 173 auto index = str.countUntil!(e => !std.ascii.isHexDigit(e)); 174 if (index != -1) 175 throw new Exception( 176 format("String '%s' has non hex character at index %s", 177 str, index)); 178 179 return BitBlob(str); 180 } 181 182 pure nothrow @nogc: 183 184 /*************************************************************************** 185 186 Create a BitBlob from binary data, e.g. serialized data 187 188 Params: 189 bin = Binary data to store in this `BitBlob`. 190 isLE = `true` if the data is little endian, `false` otherwise. 191 Internally the data will be stored in little endian. 192 193 Throws: 194 If `bin.length != typeof(this).sizeof` 195 196 ***************************************************************************/ 197 198 public this (scope const ubyte[] bin, bool isLE = true) 199 { 200 enum W = Size; // Make sure the value is shown, not the symbol 201 if (bin.length != Size) 202 assert(0, "ubyte[] argument to " ~ typeof(this).stringof 203 ~ " constructor does not match the expected size of " 204 ~ W.stringof); 205 206 this.data[] = bin[]; 207 if (!isLE) 208 { 209 foreach (cnt; 0 .. Size / 2) 210 { 211 // Not sure the frontend is clever enough to avoid bounds checks 212 this.data[cnt] ^= this.data[$ - 1 - cnt]; 213 this.data[$ - 1 - cnt] ^= this.data[cnt]; 214 this.data[cnt] ^= this.data[$ - 1 - cnt]; 215 } 216 } 217 } 218 219 /*************************************************************************** 220 221 Create a BitBlob from an hexadecimal string representation 222 223 Params: 224 hexstr = String representation of the binary data in base 16. 225 The hexadecimal prefix (0x) is optional. 226 Can be upper or lower case. 227 228 Throws: 229 If `hexstr_without_prefix.length != (typeof(this).sizeof * 2)`. 230 231 ***************************************************************************/ 232 233 public this (scope const(char)[] hexstr) 234 { 235 enum Expected = Size * 2; // Make sure the value is shown, not the symbol 236 enum ErrorMsg = "Length of string passed to " ~ typeof(this).stringof 237 ~ " constructor does not match the expected size of " ~ Expected.stringof; 238 if (hexstr.length == (Expected + "0x".length)) 239 { 240 assert(hexstr[0] == '0', ErrorMsg); 241 assert(hexstr[1] == 'x' || hexstr[1] == 'X', ErrorMsg); 242 hexstr = hexstr[2 .. $]; 243 } 244 else 245 assert(hexstr.length == Expected, ErrorMsg); 246 247 auto range = hexstr.byChar.map!(std.ascii.toLower!(char)); 248 size_t idx; 249 foreach (chunk; range.map!(fromHex).chunks(2).retro) 250 this.data[idx++] = cast(ubyte)((chunk[0] << 4) + chunk[1]); 251 } 252 253 /// Store the internal data 254 private ubyte[Size] data; 255 256 /// Returns: If this BitBlob has any value 257 public bool isNull () const 258 { 259 return this == typeof(this).init; 260 } 261 262 /// Used for sha256Of 263 public inout(ubyte)[] opIndex () inout 264 { 265 return this.data; 266 } 267 268 /// Convenience overload 269 public inout(ubyte)[] opSlice (size_t from, size_t to) inout 270 { 271 return this.data[from .. to]; 272 } 273 274 /// Ditto 275 alias opDollar = Size; 276 277 /// Public because of a visibility bug 278 public static ubyte fromHex (char c) 279 { 280 if (c >= '0' && c <= '9') 281 return cast(ubyte)(c - '0'); 282 if (c >= 'a' && c <= 'f') 283 return cast(ubyte)(10 + c - 'a'); 284 assert(0, "Unexpected char in string passed to BitBlob"); 285 } 286 287 /// Support for comparison 288 public int opCmp (ref const typeof(this) s) const 289 { 290 // Reverse because little endian 291 foreach_reverse (idx, b; this.data) 292 if (b != s.data[idx]) 293 return b - s.data[idx]; 294 return 0; 295 } 296 297 /// Support for comparison (rvalue overload) 298 public int opCmp (const typeof(this) s) const 299 { 300 return this.opCmp(s); 301 } 302 } 303 304 pure @safe nothrow @nogc unittest 305 { 306 alias Hash = BitBlob!32; 307 308 Hash gen1 = GenesisBlockHashStr; 309 Hash gen2 = GenesisBlockHash; 310 assert(gen1.data == GenesisBlockHash); 311 assert(gen1 == gen2); 312 313 Hash gm1 = GMerkle_str; 314 Hash gm2 = GMerkle_bin; 315 assert(gm1.data == GMerkle_bin); 316 // Test opIndex 317 assert(gm1[] == GMerkle_bin); 318 assert(gm1 == gm2); 319 320 Hash empty; 321 assert(empty.isNull); 322 assert(!gen1.isNull); 323 324 // Test opCmp 325 assert(empty < gen1); 326 assert(gm1 > gen2); 327 328 assert(!(gm1 > gm1)); 329 assert(!(gm1 < gm1)); 330 assert(gm1 >= gm1); 331 assert(gm1 <= gm1); 332 } 333 334 /// Test toString 335 unittest 336 { 337 import std..string : toUpper; 338 339 alias Hash = BitBlob!32; 340 Hash gen1 = GenesisBlockHashStr; 341 assert(format("%s", gen1) == GenesisBlockHashStr); 342 assert(format("%x", gen1) == GenesisBlockHashStr[2 .. $]); 343 assert(format("%X", gen1) == GenesisBlockHashStr[2 .. $].toUpper()); 344 assert(format("%w", gen1) == GenesisBlockHashStr); 345 assert(gen1.toString() == GenesisBlockHashStr); 346 assert(Hash(gen1.toString()) == gen1); 347 assert(Hash.fromString(gen1.toString()) == gen1); 348 } 349 350 /// Make sure `toString` does not allocate even if it's not `@nogc` 351 unittest 352 { 353 import core.memory; 354 alias Hash = BitBlob!32; 355 356 Hash gen1 = GenesisBlockHashStr; 357 char[Hash.StringBufferSize] buffer; 358 auto statsBefore = GC.stats(); 359 formattedWrite(buffer[], "%s", gen1); 360 auto statsAfter = GC.stats(); 361 assert(buffer == GenesisBlockHashStr); 362 assert(statsBefore.usedSize == statsAfter.usedSize); 363 } 364 365 /// Test initialization from big endian 366 @safe unittest 367 { 368 import std.algorithm.mutation : reverse; 369 ubyte[32] genesis = GenesisBlockHash; 370 genesis[].reverse; 371 auto h = BitBlob!(32)(genesis, false); 372 assert(h.toString() == GenesisBlockHashStr); 373 } 374 375 // Test assertion failure to raise code coverage 376 unittest 377 { 378 import core.exception : AssertError; 379 import std.algorithm.mutation : reverse; 380 import std.exception; 381 alias Hash = BitBlob!(32); 382 ubyte[32] genesis = GenesisBlockHash; 383 genesis[].reverse; 384 Hash result; 385 assert(collectException!AssertError(Hash(genesis[0 .. $ - 1], false)) !is null); 386 } 387 388 // Ditto 389 unittest 390 { 391 import core.exception : AssertError; 392 import std.algorithm.mutation : reverse; 393 import std.exception; 394 alias Hash = BitBlob!(32); 395 ubyte[32] genesis = GenesisBlockHash; 396 genesis[].reverse; 397 Hash h = Hash(genesis, false); 398 Hash h1 = Hash(h.toString()); 399 assert(h == h1); 400 assert(collectException!AssertError(Hash(h.toString()[0 .. $ - 1])) !is null); 401 } 402 403 // Ditto (Covers the assert(0) in `fromHex`) 404 unittest 405 { 406 alias Hash = BitBlob!(32); 407 import core.exception : AssertError; 408 import std.exception; 409 char[GenesisBlockHashStr.length] buff = GenesisBlockHashStr; 410 Hash h = Hash(buff); 411 buff[5] = '_'; // Invalid char 412 assert(collectException!AssertError(Hash(buff)) !is null); 413 } 414 415 // Test that `fromString` throws Exceptions as and when expected 416 unittest 417 { 418 import std.exception; 419 alias Hash = BitBlob!(32); 420 421 // Error on the length 422 assert(collectException!Exception(Hash.fromString("Hello world")) !is null); 423 424 char[GenesisBlockHashStr.length] buff = GenesisBlockHashStr; 425 Hash h = Hash(buff); 426 buff[5] = '_'; 427 // Error on the invalid char 428 assert(collectException!Exception(Hash.fromString(buff)) !is null); 429 } 430 431 // Make sure the string parsing works at CTFE 432 unittest 433 { 434 static immutable BitBlob!32 CTFEability = BitBlob!32(GenesisBlockHashStr); 435 static assert(CTFEability[] == GenesisBlockHash); 436 static assert(CTFEability == BitBlob!32.fromString(GenesisBlockHashStr)); 437 } 438 439 // Support for rvalue opCmp 440 unittest 441 { 442 alias Hash = BitBlob!(32); 443 import std.algorithm.sorting : sort; 444 445 static Hash getLValue(int) { return Hash.init; } 446 int[] array = [1, 2]; 447 array.sort!((a, b) => getLValue(a) < getLValue(b)); 448 } 449 450 version (unittest) 451 { 452 private: 453 /// Bitcoin's genesis block hash 454 static immutable GenesisBlockHashStr = 455 "0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f"; 456 static immutable ubyte[32] GenesisBlockHash = [ 457 0x6f, 0xe2, 0x8c, 0x0a, 0xb6, 0xf1, 0xb3, 0x72, 0xc1, 0xa6, 0xa2, 0x46, 458 0xae, 0x63, 0xf7, 0x4f, 0x93, 0x1e, 0x83, 0x65, 0xe1, 0x5a, 0x08, 0x9c, 459 0x68, 0xd6, 0x19, 0x00, 0x00, 0x00, 0x00, 0x00 ]; 460 461 /// Bitcoin's genesis block Merkle root hash 462 static immutable GMerkle_str = 463 "0X4A5E1E4BAAB89F3A32518A88C31BC87F618F76673E2CC77AB2127B7AFDEDA33B"; 464 static immutable ubyte[] GMerkle_bin = [ 465 0x3b, 0xa3, 0xed, 0xfd, 0x7a, 0x7b, 0x12, 0xb2, 0x7a, 0xc7, 0x2c, 0x3e, 466 0x67, 0x76, 0x8f, 0x61, 0x7f, 0xc8, 0x1b, 0xc3, 0x88, 0x8a, 0x51, 0x32, 467 0x3a, 0x9f, 0xb8, 0xaa, 0x4b, 0x1e, 0x5e, 0x4a ]; 468 }