Skip to content

Instantly share code, notes, and snippets.

@rikkimax

rikkimax/fixednum.d

Created February 3, 2020 03:06
Show Gist options
  • Save rikkimax/6993b8a9f22e7288424b28d5f6914a3a to your computer and use it in GitHub Desktop.
Save rikkimax/6993b8a9f22e7288424b28d5f6914a3a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
fixednum.d
module embedab.hash.fixednum;
/**
* Fixed sized unsigned big integer implementation.
*
* opBinary_Support_ulong:
* - <<
* - >>
* - &
* - +
*
* opOpAssign_Support_BigInt:
* - <<
* - >>
* - &
* - +
* - *
* - ^
* - ^^
* - |
*/
struct FixedUNum(size_t ByteCount) {
private {
static assert((ByteCount > 0) && ((ByteCount & (~ByteCount + 1)) == ByteCount) &&
ByteCount >= 16, "FixedUnum!ByteCount must have ByteCount that is power of 2 and equal or above to 16.");
enum {
BytesPerSide = ByteCount / 2,
TotalBits = ByteCount*8,
BitsPerSide = TotalBits / 2,
BitsPerSideHalf = TotalBits / 4,
}
static if (ByteCount == 16) {
ulong upper, lower;
} else {
FixedUNum!BytesPerSide upper, lower;
}
}
static if (ByteCount == 16) {
///
this(ulong lower, ulong upper=0) {
this.lower = lower;
this.upper = upper;
}
} else {
///
this(ulong lower) {
this.lower = FixedUNum!BytesPerSide(lower);
}
///
this(FixedUNum!BytesPerSide lower, FixedUNum!BytesPerSide upper=FixedUNum!BytesPerSide.init) {
this.lower = lower;
this.upper = upper;
}
}
///
void opAssign(ulong lower) {
this.lower = lower;
this.upper = 0;
}
///
void opAssign(FixedUNum!ByteCount other) {
this.lower = other.lower;
this.upper = other.upper;
}
///
FixedUNum!ByteCount opBinary(string op)(ulong value) {
FixedUNum!ByteCount ret = this;
ret.opOpAssign!(op)(value);
return ret;
}
///
FixedUNum!ByteCount opBinary(string op)(FixedUNum!ByteCount other) {
FixedUNum!ByteCount ret = this;
ret.opOpAssign!(op)(other);
return ret;
}
///
void opOpAssign(string op)(ulong value) {
static if (op == "<<") {
if (value >= TotalBits) {
this.upper = 0;
this.lower = 0;
return;
} else if (value >= BitsPerSide) {
this.upper = this.lower;
this.lower = 0;
if (value > BitsPerSide) value -= BitsPerSide;
}
if (value > 0) {
this.upper <<= value;
if (value+1 < BitsPerSide) {
foreach(i; 0 .. value)
this.upper |= (this.lower & (1 << (BitsPerSide-value))) >> (BitsPerSide-(value+1));
}
this.lower <<= value;
}
} else static if (op == ">>") {
if (value >= TotalBits) {
this.upper = 0;
this.lower = 0;
return;
} else if (value >= BitsPerSide) {
this.lower = this.upper;
this.upper = 0;
if (value > BitsPerSide) value -= BitsPerSide;
}
if (value > 0) {
this.lower >>= value;
if (value+1 < BitsPerSide) {
foreach(i; 0 .. value)
this.lower |= (this.upper & (1 << i)) << (BitsPerSide-(value+1)) ;
}
this.upper >>= value;
}
} else static if (op == "&") {
this.lower &= value;
this.upper = 0;
} else static if (op == "+") {
this.lower += value;
if (this.lower < value) this.upper++;
} else static assert(0, "unknown op");
}
///
void opOpAssign(string op)(FixedUNum!ByteCount other) {
static if (op == "+") {
this.upper += other.upper;
this.lower += other.lower;
if (this.lower < other.lower) this.upper++;
} else static if (op == "*") {
typeof(upper)
u1 = this.lower & typeof(upper).max,
v1 = other.lower & typeof(upper).max,
t = u1 * v1,
w3 = t & typeof(upper).max,
k = t >> BitsPerSideHalf;
this.lower >>= BitsPerSideHalf;
t = (this.lower * v1) + k;
k = (t & typeof(upper).max);
typeof(upper) w1 = t >> BitsPerSideHalf;
other.lower >>= BitsPerSideHalf;
t = (u1 * other.lower) + k;
k = t >> BitsPerSideHalf;
this.upper = (this.lower * other.lower) + w1 + k;
this.lower = (t << BitsPerSideHalf) + w3;
this.upper += (this.upper * other.lower) + (this.lower * other.upper);
} else static if (op == "^^") {
FixedUNum!ByteCount by = this;
FixedUNum!ByteCount counter = FixedUNum!ByteCount(0);
while(counter < other) {
this *= by;
counter += FixedUNum!ByteCount(1);
}
} else static if (op == "&") {
this.upper &= other.upper;
this.lower &= other.lower;
} else static if (op == "^") {
this.upper ^= other.upper;
this.lower ^= other.lower;
} else static if (op == "|") {
this.upper |= other.upper;
this.lower |= other.lower;
} else static assert(0, "unkown op");
}
///
int opCmp(FixedUNum!ByteCount other) {
if (other.upper > this.upper) return -1;
else if (other.upper < this.upper) return 1;
else if (other.lower > this.lower) return -1;
else if (other.lower < this.lower) return 1;
else return 0;
}
@property {
static if (ByteCount == 16) {
enum {
///
min = 0,
///
max = 0xFFFFFFFF
}
} else static if (ByteCount == 32) {
enum {
///
min = FixedUNum!ByteCount(0),
///
max = FixedUNum!ByteCount(FixedUNum!BytesPerSide(0xFFFFFFFF, 0xFFFFFFFF), FixedUNum!BytesPerSide(0xFFFFFFFF, 0xFFFFFFFF))
}
} else static if (ByteCount > 32) {
enum {
///
min = FixedUNum!ByteCount(0),
///
max = FixedUNum!ByteCount(FixedUNum!BytesPerSide.max, FixedUNum!BytesPerSide.max)
}
}
///
ubyte[ByteCount] bytes() {
ubyte[ByteCount] ret;
static if (ByteCount == 16) {
import std.bitmanip : nativeToLittleEndian;
ret[0 .. 8] = nativeToLittleEndian(this.lower);
ret[8 .. 16] = nativeToLittleEndian(this.upper);
} else {
ret[0 .. ByteCount / 2] = this.lower.bytes;
ret[ByteCount / 2 .. ByteCount] = this.upper.bytes;
}
return ret;
}
}
}
unittest {
auto v16 = FixedUNum!16(170);
assert(v16.bytes == [170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v16 >>= 2;
assert(v16.bytes == [42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v16 >>= 2;
assert(v16.bytes == [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v16 <<= 2;
assert(v16.bytes == [40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
auto v32 = FixedUNum!32(170);
assert(v32.bytes == [170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v32 >>= 2;
assert(v32.bytes == [42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v32 >>= 2;
assert(v32.bytes == [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v32 <<= 2;
assert(v32.bytes == [40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
auto v64 = FixedUNum!64(170);
assert(v64.bytes == [170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v64 >>= 2;
assert(v64.bytes == [42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v64 >>= 2;
assert(v64.bytes == [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
v64 <<= 2;
assert(v64.bytes == [40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
}
Raw
fnv.d
/**
* Performs a Fowler–Noll–Vo hash algorithms
*
* Supports 0, 1 and 1a in the bit depths of 32, 64, 128 and 256.
*/
module embedab.hash.fnv;
import embedab.hash.fixednum;
private enum {
FNV_Prime_32 = (2^^24) + (2^^8) + 0x93,
FNV_Offset_Basis_32 = 0x811c9dc5,
FNV_Prime_64 = (2^^40) + (2^^8) + 0xb3,
FNV_Offset_Basis_64 = 0xcbf29ce484222325,
FNV_Prime_128 = (FixedUNum!16(2)^^FixedUNum!16(88)) + (FixedUNum!16(2)^^FixedUNum!16(8)) + FixedUNum!16(0x3b),
FNV_Offset_Basis_128 = FixedUNum!16(0x6c62272e07bb0142, 0x62b821756295c58d),
FNV_Prime_256 = (FixedUNum!32(2)^^FixedUNum!32(168)) + (FixedUNum!32(2)^^FixedUNum!32(8)) + FixedUNum!32(0x63),
FNV_Offset_Basis_256 = FixedUNum!32(FixedUNum!16(0xdd268dbcaac55036, 0x2d98c384c4e576cc), FixedUNum!16(0xc8b1536847b6bbb3, 0x1023b4c8caee0535)),
}
/**
* Performs a Fowler–Noll–Vo 0 hash
*
* Params:
* data = The data to hash
* start = Start hash (for incremental hashing)
*
* Returns:
* The hash
*/
uint fnv_32_0(ubyte[] data, uint start=0) {
uint hash = start;
foreach(b; data) {
hash *= FNV_Prime_32;
hash ^= b;
}
return hash;
}
/// Ditto
ulong fnv_64_0(ubyte[] data, ulong start=0) {
ulong hash = start;
foreach(b; data) {
hash *= FNV_Prime_64;
hash ^= b;
}
return hash;
}
/// Ditto
FixedUNum!16 fnv_128_0(ubyte[] data, FixedUNum!16 start=FixedUNum!16(0)) {
FixedUNum!16 hash = start;
foreach(b; data) {
hash *= FNV_Prime_128;
hash ^= FixedUNum!16(b);
}
return hash;
}
/// Ditto
FixedUNum!32 fnv_256_0(ubyte[] data, FixedUNum!32 start=FixedUNum!32(0)) {
FixedUNum!32 hash = start;
foreach(b; data) {
hash *= FNV_Prime_256;
hash ^= FixedUNum!32(b);
}
return hash;
}
/**
* Performs a Fowler–Noll–Vo 1 hash
*
* Params:
* data = The data to hash
* start = Start hash (for incremental hashing)
*
* Returns:
* The hash
*/
uint fnv_32_1(ubyte[] data, uint start=FNV_Offset_Basis_32) {
uint hash = start;
foreach(b; data) {
hash *= FNV_Prime_32;
hash ^= b;
}
return hash;
}
/// Ditto
ulong fnv_64_1(ubyte[] data, ulong start=FNV_Offset_Basis_64) {
ulong hash = start;
foreach(b; data) {
hash *= FNV_Prime_64;
hash ^= b;
}
return hash;
}
/// Ditto
FixedUNum!16 fnv_128_1(ubyte[] data, FixedUNum!16 start=FNV_Offset_Basis_128) {
FixedUNum!16 hash = start;
foreach(b; data) {
hash *= FNV_Prime_128;
hash ^= FixedUNum!16(b);
}
return hash;
}
/// Ditto
FixedUNum!32 fnv_256_1(ubyte[] data, FixedUNum!32 start=FNV_Offset_Basis_256) {
FixedUNum!32 hash = start;
foreach(b; data) {
hash *= FNV_Prime_256;
hash ^= FixedUNum!32(b);
}
return hash;
}
/**
* Performs a Fowler–Noll–Vo 1a hash
*
* Params:
* data = The data to hash
* start = Start hash (for incremental hashing)
*
* Returns:
* The hash
*/
uint fnv_32_1a(ubyte[] data, uint start=FNV_Offset_Basis_32) {
uint hash = start;
foreach(b; data) {
hash ^= b;
hash *= FNV_Prime_32;
}
return hash;
}
/// Ditto
ulong fnv_64_1a(ubyte[] data, ulong start=FNV_Offset_Basis_64) {
ulong hash = start;
foreach(b; data) {
hash ^= b;
hash *= FNV_Prime_64;
}
return hash;
}
/// Ditto
FixedUNum!16 fnv_128_1a(ubyte[] data, FixedUNum!16 start=FNV_Offset_Basis_128) {
FixedUNum!16 hash = start;
foreach(b; data) {
hash ^= FixedUNum!16(b);
hash *= FNV_Prime_128;
}
return hash;
}
/// Ditto
FixedUNum!32 fnv_128_1a(ubyte[] data, FixedUNum!32 start=FNV_Offset_Basis_256) {
FixedUNum!32 hash = start;
foreach(b; data) {
hash ^= FixedUNum!32(b);
hash *= FNV_Prime_256;
}
return hash;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment