From f1bc4dc2e202c7103e199a9331c9b0e93bd6c8ec Mon Sep 17 00:00:00 2001 From: Eugen Wissner Date: Mon, 19 Dec 2016 16:33:16 +0100 Subject: Add length and opCmp to the Queue --- source/tanya/container/bit.d | 510 --------------------------------------- source/tanya/container/entry.d | 45 ++++ source/tanya/container/list.d | 83 ++----- source/tanya/container/package.d | 1 - source/tanya/container/queue.d | 205 ++++++++++++---- source/tanya/crypto/bit.d | 510 +++++++++++++++++++++++++++++++++++++++ source/tanya/crypto/des.d | 2 +- source/tanya/crypto/package.d | 10 +- source/tanya/memory/allocator.d | 21 +- 9 files changed, 757 insertions(+), 630 deletions(-) delete mode 100644 source/tanya/container/bit.d create mode 100644 source/tanya/container/entry.d create mode 100644 source/tanya/crypto/bit.d (limited to 'source') diff --git a/source/tanya/container/bit.d b/source/tanya/container/bit.d deleted file mode 100644 index 88c563f..0000000 --- a/source/tanya/container/bit.d +++ /dev/null @@ -1,510 +0,0 @@ -/* This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -/** - * Copyright: Eugene Wissner 2016. - * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/, - * Mozilla Public License, v. 2.0). - * Authors: $(LINK2 mailto:belka@caraus.de, Eugene Wissner) - */ -module tanya.container.bit; - -/** - * Wrapper that allows bit manipulation on $(D_KEYWORD ubyte[]) array. - */ -struct BitVector -{ - protected ubyte[] vector; - - /** - * Params: - * array = Array should be manipulated on. - */ - this(inout(ubyte[]) array) inout pure nothrow @safe @nogc - in - { - assert(array.length <= size_t.max / 8); - assert(array !is null); - } - body - { - vector = array; - } - - /// - unittest - { - ubyte[5] array1 = [234, 3, 252, 10, 18]; - ubyte[3] array2 = [65, 13, 173]; - auto bits = BitVector(array1); - - assert(bits[] is array1); - assert(bits[] !is array2); - - bits = BitVector(array2); - assert(bits[] is array2); - - } - - /** - * Returns: Number of bits in the vector. - */ - @property inout(size_t) length() inout const pure nothrow @safe @nogc - { - return vector.length * 8; - } - - /// Ditto. - inout(size_t) opDollar() inout const pure nothrow @safe @nogc - { - return vector.length * 8; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] arr = [65, 13, 173]; - auto bits = BitVector(arr); - - assert(bits.length == 24); - } - - /** - * Params: - * bit = Bit position. - * - * Returns: $(D_KEYWORD true) if the bit on position $(D_PARAM bit) is set, - * $(D_KEYWORD false) if not set. - */ - inout(bool) opIndex(size_t bit) inout const pure nothrow @safe @nogc - in - { - assert(bit / 8 <= vector.length); - } - body - { - return (vector[bit / 8] & (0x80 >> (bit % 8))) != 0; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] arr = [65, 13, 173]; - auto bits = BitVector(arr); - - assert(!bits[0]); - assert(bits[1]); - assert(bits[7]); - assert(!bits[8]); - assert(!bits[11]); - assert(bits[12]); - assert(bits[20]); - assert(bits[23]); - } - - /** - * Returns: Underlying array. - */ - inout(ubyte[]) opIndex() inout pure nothrow @safe @nogc - { - return vector; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] arr = [65, 13, 173]; - auto bits = BitVector(arr); - - assert(bits[] is arr); - } - - /** - * Params: - * value = $(D_KEYWORD true) if the bit should be set, - * $(D_KEYWORD false) if cleared. - * bit = Bit position. - * - * Returns: $(D_PSYMBOL this). - */ - bool opIndexAssign(bool value, size_t bit) pure nothrow @safe @nogc - in - { - assert(bit / 8 <= vector.length); - } - body - { - if (value) - { - vector[bit / 8] |= (0x80 >> (bit % 8)); - } - else - { - vector[bit / 8] &= ~(0x80 >> (bit % 8)); - } - return value; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] arr = [65, 13, 173]; - auto bits = BitVector(arr); - - bits[5] = bits[6] = true; - assert(bits[][0] == 71); - - bits[14] = true; - bits[15] = false; - assert(bits[][1] == 14); - - bits[16] = bits[23] = false; - assert(bits[][2] == 44); - } - - /** - * Copies bits from $(D_PARAM vector) into this $(D_PSYMBOL BitVector). - * - * The array that should be assigned, can be smaller (but not larger) than - * the underlying array of this $(D_PSYMBOL BitVector), leading zeros will - * be added in this case to the left. - * - * Params: - * vector = $(D_KEYWORD ubyte[]) array not larger than - * `$(D_PSYMBOL length) / 8`. - * - * Returns: $(D_KEYWORD this). - */ - BitVector opAssign(ubyte[] vector) pure nothrow @safe @nogc - in - { - assert(vector.length <= this.vector.length); - } - body - { - immutable delta = this.vector.length - vector.length; - if (delta > 0) - { - this.vector[0..delta] = 0; - } - this.vector[delta..$] = vector[0..$]; - return this; - } - - /// - unittest - { - ubyte[5] array1 = [234, 3, 252, 10, 18]; - ubyte[3] array2 = [65, 13, 173]; - auto bits = BitVector(array1); - - bits = array2; - assert(bits[][0] == 0); - assert(bits[][1] == 0); - assert(bits[][2] == 65); - assert(bits[][3] == 13); - assert(bits[][4] == 173); - - bits = array2[0..2]; - assert(bits[][0] == 0); - assert(bits[][1] == 0); - assert(bits[][2] == 0); - assert(bits[][3] == 65); - assert(bits[][4] == 13); - } - - /** - * Support for bitwise operations. - * - * Params: - * that = Another bit vector. - * - * Returns: $(D_KEYWORD this). - */ - BitVector opOpAssign(string op)(BitVector that) pure nothrow @safe @nogc - if ((op == "^") || (op == "|") || (op == "&")) - { - return opOpAssign(op)(that.vector); - } - - /// Ditto. - BitVector opOpAssign(string op)(ubyte[] that) pure nothrow @safe @nogc - if ((op == "^") || (op == "|") || (op == "&")) - in - { - assert(that.length <= vector.length); - } - body - { - for (int i = cast(int) vector.length - 1; i >= 0; --i) - { - mixin("vector[i] " ~ op ~ "= " ~ "that[i];"); - } - immutable delta = vector.length - that.length; - if (delta) - { - static if (op == "&") - { - vector[0..delta] = 0; - } - } - return this; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] array1 = [65, 13, 173]; - ubyte[3] array2 = [0b01010010, 0b10111110, 0b10111110]; - auto bits = BitVector(array1); - - bits |= array2; - assert(bits[][0] == 0b01010011); - assert(bits[][1] == 0b10111111); - assert(bits[][2] == 0b10111111); - - bits &= array2; - assert(bits[][0] == array2[0]); - assert(bits[][1] == array2[1]); - assert(bits[][2] == array2[2]); - - bits ^= array2; - assert(bits[][0] == 0); - assert(bits[][1] == 0); - assert(bits[][2] == 0); - } - - /** - * Support for shift operations. - * - * Params: - * n = Number of bits. - * - * Returns: $(D_KEYWORD this). - */ - BitVector opOpAssign(string op)(in size_t n) pure nothrow @safe @nogc - if ((op == "<<") || (op == ">>")) - - { - if (n >= length) - { - vector[0..$] = 0; - } - else if (n != 0) - { - immutable bit = n % 8, step = n / 8; - immutable delta = 8 - bit; - size_t i, j; - - static if (op == "<<") - { - for (j = step; j < vector.length - 1; ++i) - { - vector[i] = cast(ubyte)((vector[j] << bit) - | vector[++j] >> delta); - } - vector[i] = cast(ubyte)(vector[j] << bit); - vector[$ - step ..$] = 0; - } - else static if (op == ">>") - { - for (i = vector.length - 1, j = i - step; j > 0; --i) - { - vector[i] = cast(ubyte)((vector[j] >> bit) - | vector[--j] << delta); - } - vector[i] = cast(ubyte)(vector[j] >> bit); - vector[0..step] = 0; - } - } - return this; - } - - /// - nothrow @safe @nogc unittest - { - ubyte[4] arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011]; - auto bits = BitVector(arr); - - bits <<= 0; - assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010 - && bits[][2] == 0b01010010 && bits[][3] == 0b01010011); - - bits <<= 2; - assert(bits[][0] == 0b11111011 && bits[][1] == 0b11001001 - && bits[][2] == 0b01001001 && bits[][3] == 0b01001100); - - bits <<= 4; - assert(bits[][0] == 0b10111100 && bits[][1] == 0b10010100 - && bits[][2] == 0b10010100 && bits[][3] == 0b11000000); - - bits <<= 8; - assert(bits[][0] == 0b10010100 && bits[][1] == 0b10010100 - && bits[][2] == 0b11000000 && bits[][3] == 0b00000000); - - bits <<= 7; - assert(bits[][0] == 0b01001010 && bits[][1] == 0b01100000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - - bits <<= 25; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - - arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101]; - bits <<= 24; - assert(bits[][0] == 0b01010101 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - - arr[1] = 0b11001100; - arr[2] = 0b11111111; - arr[3] = 0b01010101; - bits <<= 12; - assert(bits[][0] == 0b11001111 && bits[][1] == 0b11110101 - && bits[][2] == 0b01010000 && bits[][3] == 0b00000000); - - bits <<= 100; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - - arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011]; - bits >>= 0; - assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010 - && bits[][2] == 0b01010010 && bits[][3] == 0b01010011); - - bits >>= 2; - assert(bits[][0] == 0b00101111 && bits[][1] == 0b10111100 - && bits[][2] == 0b10010100 && bits[][3] == 0b10010100); - - bits >>= 4; - assert(bits[][0] == 0b00000010 && bits[][1] == 0b11111011 - && bits[][2] == 0b11001001 && bits[][3] == 0b01001001); - - bits >>= 8; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000010 - && bits[][2] == 0b11111011 && bits[][3] == 0b11001001); - - bits >>= 7; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000101 && bits[][3] == 0b11110111); - - bits >>= 25; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - - arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101]; - bits >>= 24; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00110011); - - arr[1] = 0b11001100; - arr[2] = 0b11111111; - arr[3] = 0b01010101; - bits >>= 12; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00001100 && bits[][3] == 0b11001111); - - bits >>= 100; - assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 - && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); - } - - /** - * Negates all bits. - * - * Returns: $(D_KEYWORD this). - */ - BitVector opUnary(string op)() pure nothrow @safe @nogc - if (op == "~") - { - foreach (ref b; vector) - { - b = ~b; - } - return this; - } - - /// - unittest - { - // [01000001, 00001101, 10101101] - ubyte[3] arr = [65, 13, 173]; - auto bits = BitVector(arr); - - ~bits; - assert(bits[][0] == 0b10111110); - assert(bits[][1] == 0b11110010); - assert(bits[][2] == 0b01010010); - } - - /** - * Iterates through all bits. - * - * Params: - * dg = $(D_KEYWORD foreach) delegate. - * - * Returns: By $(D_PARAM dg) returned value. - */ - int opApply(int delegate(size_t, bool) dg) - { - int result; - foreach (i, ref v; vector) - { - foreach (c; 0..8) - { - result = dg(i * 8 + c, (v & (0x80 >> c)) != 0); - if (result) - { - return result; - } - } - } - return result; - } - - /// Ditto. - int opApply(int delegate(bool) dg) - { - int result; - foreach (ref v; vector) - { - foreach (c; 0..8) - { - result = dg((v & (0x80 >> c)) != 0); - if (result) - { - return result; - } - } - } - return result; - } - - /// - unittest - { - ubyte[2] arr = [0b01000001, 0b00001101]; - auto bits = BitVector(arr); - size_t c; - - foreach (i, v; bits) - { - assert(i == c); - if (i == 1 || i == 7 || i == 15 || i == 13 || i == 12) - { - assert(v); - } - else - { - assert(!v); - } - ++c; - } - assert(c == 16); - } -} diff --git a/source/tanya/container/entry.d b/source/tanya/container/entry.d new file mode 100644 index 0000000..ce267a0 --- /dev/null +++ b/source/tanya/container/entry.d @@ -0,0 +1,45 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * Internal package used by containers that rely on entries/nodes. + * + * Copyright: Eugene Wissner 2016. + * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/, + * Mozilla Public License, v. 2.0). + * Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner) + */ +module tanya.container.entry; + +version (unittest) +{ + package struct ConstEqualsStruct + { + int opEquals(typeof(this) that) const + { + return true; + } + } + + package struct MutableEqualsStruct + { + int opEquals(typeof(this) that) + { + return true; + } + } + + package struct NoEqualsStruct + { + } +} + +package struct Entry(T) +{ + /// Item content. + T content; + + /// Next item. + Entry* next; +} diff --git a/source/tanya/container/list.d b/source/tanya/container/list.d index 0ce7e4f..d0691ee 100644 --- a/source/tanya/container/list.d +++ b/source/tanya/container/list.d @@ -10,28 +10,17 @@ */ module tanya.container.list; +import tanya.container.entry; import tanya.memory; /** - * Singly linked list. + * Singly-linked list. * * Params: * T = Content type. */ -class SList(T) +struct SList(T) { - /** - * Creates a new $(D_PSYMBOL SList). - * - * Params: - * allocator = The allocator should be used for the element - * allocations. - */ - this(shared Allocator allocator = defaultAllocator) - { - this.allocator = allocator; - } - /** * Removes all elements from the list. */ @@ -41,7 +30,7 @@ class SList(T) } /** - * Remove all contents from the $(D_PSYMBOL SList). + * Removes all contents from the list. */ void clear() { @@ -54,14 +43,12 @@ class SList(T) /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; l.insertFront(8); l.insertFront(5); l.clear(); assert(l.empty); - - dispose(defaultAllocator, l); } /** @@ -83,35 +70,39 @@ class SList(T) * Params: * x = New element. */ - void insertFront(T x) + void insertFront(ref T x) { - Entry* temp = make!Entry(allocator); + auto temp = allocator.make!(Entry!T); temp.content = x; temp.next = first.next; first.next = temp; } + /// Ditto. + void insertFront(T x) + { + insertFront(x); + } + /// Ditto. alias insert = insertFront; /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; l.insertFront(8); assert(l.front == 8); l.insertFront(9); assert(l.front == 9); - - dispose(defaultAllocator, l); } /** * Returns: $(D_KEYWORD true) if the list is empty. */ - @property bool empty() inout const + @property bool empty() const { return first.next is null; } @@ -121,7 +112,7 @@ class SList(T) * * Returns: The first element. */ - T popFront() + void popFront() in { assert(!empty); @@ -129,26 +120,21 @@ class SList(T) body { auto n = first.next.next; - auto content = first.next.content; - dispose(allocator, first.next); + allocator.dispose(first.next); first.next = n; - - return content; } /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; l.insertFront(8); l.insertFront(9); assert(l.front == 9); l.popFront(); assert(l.front == 8); - - dispose(defaultAllocator, l); } /** @@ -179,7 +165,7 @@ class SList(T) /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; l.insertFront(8); l.insertFront(5); @@ -188,8 +174,6 @@ class SList(T) assert(l.removeFront(2) == 2); assert(l.removeFront(3) == 1); assert(l.removeFront(3) == 0); - - dispose(defaultAllocator, l); } /** @@ -235,7 +219,7 @@ class SList(T) /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; l.insertFront(5); l.insertFront(4); @@ -246,32 +230,18 @@ class SList(T) assert(i != 1 || e == 4); assert(i != 2 || e == 5); } - dispose(defaultAllocator, l); - } - - /** - * List entry. - */ - protected struct Entry - { - /// List item content. - T content; - - /// Next list item. - Entry* next; } /// 0th element of the list. - protected Entry first; + private Entry!T first; - /// Allocator. - protected shared Allocator allocator; + mixin DefaultAllocator; } /// unittest { - auto l = make!(SList!int)(defaultAllocator); + SList!int l; size_t i; l.insertFront(5); @@ -285,8 +255,6 @@ unittest ++i; } assert(i == 3); - - dispose(defaultAllocator, l); } private unittest @@ -294,8 +262,5 @@ private unittest interface Stuff { } - - auto l = make!(SList!Stuff)(defaultAllocator); - - dispose(defaultAllocator, l); + static assert(is(SList!Stuff)); } diff --git a/source/tanya/container/package.d b/source/tanya/container/package.d index e1a5205..eba95a7 100644 --- a/source/tanya/container/package.d +++ b/source/tanya/container/package.d @@ -10,7 +10,6 @@ */ module tanya.container; -public import tanya.container.bit; public import tanya.container.buffer; public import tanya.container.list; public import tanya.container.vector; diff --git a/source/tanya/container/queue.d b/source/tanya/container/queue.d index 960254b..6470044 100644 --- a/source/tanya/container/queue.d +++ b/source/tanya/container/queue.d @@ -6,32 +6,22 @@ * Copyright: Eugene Wissner 2016. * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/, * Mozilla Public License, v. 2.0). - * Authors: $(LINK2 mailto:belka@caraus.de, Eugene Wissner) + * Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner) */ module tanya.container.queue; +import tanya.container.entry; +import std.traits; import tanya.memory; /** - * Queue. + * FIFO queue. * * Params: * T = Content type. */ struct Queue(T) { - /** - * Creates a new $(D_PSYMBOL Queue). - * - * Params: - * allocator = The allocator should be used for the element - * allocations. - */ - this(shared Allocator allocator) - { - this.allocator = allocator; - } - /** * Removes all elements from the queue. */ @@ -54,15 +44,147 @@ struct Queue(T) /// unittest { - auto q = defaultAllocator.make!(Queue!int); + Queue!int q; assert(q.empty); q.insertBack(8); q.insertBack(9); q.clear(); assert(q.empty); + } - defaultAllocator.dispose(q); + /** + * Returns how many elements are in the queue. It iterates through the queue + * to count the elements. + * + * Returns: How many elements are in the queue. + */ + size_t length() const + { + size_t len; + for (const(Entry!T)* i = first.next; i !is null; i = i.next) + { + ++len; + } + return len; + } + + /// + unittest + { + Queue!int q; + + assert(q.length == 0); + q.insertBack(5); + assert(q.length == 1); + q.insertBack(4); + assert(q.length == 2); + q.insertBack(9); + assert(q.length == 3); + + q.popFront(); + assert(q.length == 2); + q.popFront(); + assert(q.length == 1); + q.popFront(); + assert(q.length == 0); + } + + version (D_Ddoc) + { + /** + * Compares two queues. Checks if all elements of the both queues are equal. + * + * Returns: Whether $(D_KEYWORD this) and $(D_PARAM that) are equal. + */ + int opEquals(ref typeof(this) that); + + /// Ditto. + int opEquals(typeof(this) that); + } + else static if (!hasMember!(T, "opEquals") + || (functionAttributes!(T.opEquals) & FunctionAttribute.const_)) + { + bool opEquals(in ref typeof(this) that) const + { + const(Entry!T)* i = first.next; + const(Entry!T)* j = that.first.next; + while (i !is null && j !is null) + { + if (i.content != j.content) + { + return false; + } + i = i.next; + j = j.next; + } + return i is null && j is null; + } + + /// Ditto. + bool opEquals(in typeof(this) that) const + { + return opEquals(that); + } + } + else + { + /** + * Compares two queues. Checks if all elements of the both queues are equal. + * + * Returns: How many elements are in the queue. + */ + bool opEquals(ref typeof(this) that) + { + Entry!T* i = first.next; + Entry!T* j = that.first.next; + while (i !is null && j !is null) + { + if (i.content != j.content) + { + return false; + } + i = i.next; + j = j.next; + } + return i is null && j is null; + } + + /// Ditto. + bool opEquals(typeof(this) that) + { + return opEquals(that); + } + } + + /// + unittest + { + Queue!int q1, q2; + + q1.insertBack(5); + q1.insertBack(4); + q2.insertBack(5); + assert(q1 != q2); + q2.insertBack(4); + assert(q1 == q2); + + q2.popFront(); + assert(q1 != q2); + + q1.popFront(); + assert(q1 == q2); + + q1.popFront(); + q2.popFront(); + assert(q1 == q2); + } + + private unittest + { + static assert(is(Queue!ConstEqualsStruct)); + static assert(is(Queue!MutableEqualsStruct)); + static assert(is(Queue!NoEqualsStruct)); } /** @@ -84,13 +206,9 @@ struct Queue(T) * Params: * x = New element. */ - void insertBack(T x) + void insertBack(ref T x) { - if (allocator is null) - { - allocator = defaultAllocator; - } - Entry* temp = make!Entry(allocator); + auto temp = allocator.make!(Entry!T); temp.content = x; @@ -105,27 +223,31 @@ struct Queue(T) } } + /// Ditto. + void insertBack(T x) + { + insertBack(x); + } + /// Ditto. alias insert = insertBack; /// unittest { - auto q = make!(Queue!int)(defaultAllocator); + Queue!int q; assert(q.empty); q.insertBack(8); assert(q.front == 8); q.insertBack(9); assert(q.front == 8); - - dispose(defaultAllocator, q); } /** * Returns: $(D_KEYWORD true) if the queue is empty. */ - @property bool empty() inout const pure nothrow @safe + @property bool empty() const { return first.next is null; } @@ -133,14 +255,12 @@ struct Queue(T) /// unittest { - auto q = make!(Queue!int)(defaultAllocator); + Queue!int q; int value = 7; assert(q.empty); q.insertBack(value); assert(!q.empty); - - dispose(defaultAllocator, q); } /** @@ -163,15 +283,13 @@ struct Queue(T) /// unittest { - auto q = make!(Queue!int)(defaultAllocator); + Queue!int q; q.insertBack(8); q.insertBack(9); assert(q.front == 8); q.popFront(); assert(q.front == 9); - - dispose(defaultAllocator, q); } /** @@ -215,7 +333,7 @@ struct Queue(T) /// unittest { - auto q = Queue!int(defaultAllocator); + Queue!int q; size_t j; q.insertBack(5); @@ -246,32 +364,19 @@ struct Queue(T) assert(q.empty); } - /** - * Queue entry. - */ - protected struct Entry - { - /// Queue item content. - T content; - - /// Next list item. - Entry* next; - } - /// The first element of the list. - protected Entry first; + private Entry!T first; /// The last element of the list. - protected Entry* rear; + private Entry!T* rear; - /// The allocator. - protected shared Allocator allocator; + mixin DefaultAllocator; } /// unittest { - auto q = Queue!int(defaultAllocator); + Queue!int q; q.insertBack(5); assert(!q.empty); diff --git a/source/tanya/crypto/bit.d b/source/tanya/crypto/bit.d new file mode 100644 index 0000000..8610577 --- /dev/null +++ b/source/tanya/crypto/bit.d @@ -0,0 +1,510 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/** + * Copyright: Eugene Wissner 2016. + * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/, + * Mozilla Public License, v. 2.0). + * Authors: $(LINK2 mailto:belka@caraus.de, Eugene Wissner) + */ +module tanya.crypto.bit; + +/** + * Wrapper that allows bit manipulation on $(D_KEYWORD ubyte[]) array. + */ +struct BitVector +{ + protected ubyte[] vector; + + /** + * Params: + * array = Array should be manipulated on. + */ + this(inout(ubyte[]) array) inout pure nothrow @safe @nogc + in + { + assert(array.length <= size_t.max / 8); + assert(array !is null); + } + body + { + vector = array; + } + + /// + unittest + { + ubyte[5] array1 = [234, 3, 252, 10, 18]; + ubyte[3] array2 = [65, 13, 173]; + auto bits = BitVector(array1); + + assert(bits[] is array1); + assert(bits[] !is array2); + + bits = BitVector(array2); + assert(bits[] is array2); + + } + + /** + * Returns: Number of bits in the vector. + */ + @property inout(size_t) length() inout const pure nothrow @safe @nogc + { + return vector.length * 8; + } + + /// Ditto. + inout(size_t) opDollar() inout const pure nothrow @safe @nogc + { + return vector.length * 8; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] arr = [65, 13, 173]; + auto bits = BitVector(arr); + + assert(bits.length == 24); + } + + /** + * Params: + * bit = Bit position. + * + * Returns: $(D_KEYWORD true) if the bit on position $(D_PARAM bit) is set, + * $(D_KEYWORD false) if not set. + */ + inout(bool) opIndex(size_t bit) inout const pure nothrow @safe @nogc + in + { + assert(bit / 8 <= vector.length); + } + body + { + return (vector[bit / 8] & (0x80 >> (bit % 8))) != 0; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] arr = [65, 13, 173]; + auto bits = BitVector(arr); + + assert(!bits[0]); + assert(bits[1]); + assert(bits[7]); + assert(!bits[8]); + assert(!bits[11]); + assert(bits[12]); + assert(bits[20]); + assert(bits[23]); + } + + /** + * Returns: Underlying array. + */ + inout(ubyte[]) opIndex() inout pure nothrow @safe @nogc + { + return vector; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] arr = [65, 13, 173]; + auto bits = BitVector(arr); + + assert(bits[] is arr); + } + + /** + * Params: + * value = $(D_KEYWORD true) if the bit should be set, + * $(D_KEYWORD false) if cleared. + * bit = Bit position. + * + * Returns: $(D_PSYMBOL this). + */ + bool opIndexAssign(bool value, size_t bit) pure nothrow @safe @nogc + in + { + assert(bit / 8 <= vector.length); + } + body + { + if (value) + { + vector[bit / 8] |= (0x80 >> (bit % 8)); + } + else + { + vector[bit / 8] &= ~(0x80 >> (bit % 8)); + } + return value; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] arr = [65, 13, 173]; + auto bits = BitVector(arr); + + bits[5] = bits[6] = true; + assert(bits[][0] == 71); + + bits[14] = true; + bits[15] = false; + assert(bits[][1] == 14); + + bits[16] = bits[23] = false; + assert(bits[][2] == 44); + } + + /** + * Copies bits from $(D_PARAM vector) into this $(D_PSYMBOL BitVector). + * + * The array that should be assigned, can be smaller (but not larger) than + * the underlying array of this $(D_PSYMBOL BitVector), leading zeros will + * be added in this case to the left. + * + * Params: + * vector = $(D_KEYWORD ubyte[]) array not larger than + * `$(D_PSYMBOL length) / 8`. + * + * Returns: $(D_KEYWORD this). + */ + BitVector opAssign(ubyte[] vector) pure nothrow @safe @nogc + in + { + assert(vector.length <= this.vector.length); + } + body + { + immutable delta = this.vector.length - vector.length; + if (delta > 0) + { + this.vector[0..delta] = 0; + } + this.vector[delta..$] = vector[0..$]; + return this; + } + + /// + unittest + { + ubyte[5] array1 = [234, 3, 252, 10, 18]; + ubyte[3] array2 = [65, 13, 173]; + auto bits = BitVector(array1); + + bits = array2; + assert(bits[][0] == 0); + assert(bits[][1] == 0); + assert(bits[][2] == 65); + assert(bits[][3] == 13); + assert(bits[][4] == 173); + + bits = array2[0..2]; + assert(bits[][0] == 0); + assert(bits[][1] == 0); + assert(bits[][2] == 0); + assert(bits[][3] == 65); + assert(bits[][4] == 13); + } + + /** + * Support for bitwise operations. + * + * Params: + * that = Another bit vector. + * + * Returns: $(D_KEYWORD this). + */ + BitVector opOpAssign(string op)(BitVector that) pure nothrow @safe @nogc + if ((op == "^") || (op == "|") || (op == "&")) + { + return opOpAssign(op)(that.vector); + } + + /// Ditto. + BitVector opOpAssign(string op)(ubyte[] that) pure nothrow @safe @nogc + if ((op == "^") || (op == "|") || (op == "&")) + in + { + assert(that.length <= vector.length); + } + body + { + for (int i = cast(int) vector.length - 1; i >= 0; --i) + { + mixin("vector[i] " ~ op ~ "= " ~ "that[i];"); + } + immutable delta = vector.length - that.length; + if (delta) + { + static if (op == "&") + { + vector[0..delta] = 0; + } + } + return this; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] array1 = [65, 13, 173]; + ubyte[3] array2 = [0b01010010, 0b10111110, 0b10111110]; + auto bits = BitVector(array1); + + bits |= array2; + assert(bits[][0] == 0b01010011); + assert(bits[][1] == 0b10111111); + assert(bits[][2] == 0b10111111); + + bits &= array2; + assert(bits[][0] == array2[0]); + assert(bits[][1] == array2[1]); + assert(bits[][2] == array2[2]); + + bits ^= array2; + assert(bits[][0] == 0); + assert(bits[][1] == 0); + assert(bits[][2] == 0); + } + + /** + * Support for shift operations. + * + * Params: + * n = Number of bits. + * + * Returns: $(D_KEYWORD this). + */ + BitVector opOpAssign(string op)(in size_t n) pure nothrow @safe @nogc + if ((op == "<<") || (op == ">>")) + + { + if (n >= length) + { + vector[0..$] = 0; + } + else if (n != 0) + { + immutable bit = n % 8, step = n / 8; + immutable delta = 8 - bit; + size_t i, j; + + static if (op == "<<") + { + for (j = step; j < vector.length - 1; ++i) + { + vector[i] = cast(ubyte)((vector[j] << bit) + | vector[++j] >> delta); + } + vector[i] = cast(ubyte)(vector[j] << bit); + vector[$ - step ..$] = 0; + } + else static if (op == ">>") + { + for (i = vector.length - 1, j = i - step; j > 0; --i) + { + vector[i] = cast(ubyte)((vector[j] >> bit) + | vector[--j] << delta); + } + vector[i] = cast(ubyte)(vector[j] >> bit); + vector[0..step] = 0; + } + } + return this; + } + + /// + nothrow @safe @nogc unittest + { + ubyte[4] arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011]; + auto bits = BitVector(arr); + + bits <<= 0; + assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010 + && bits[][2] == 0b01010010 && bits[][3] == 0b01010011); + + bits <<= 2; + assert(bits[][0] == 0b11111011 && bits[][1] == 0b11001001 + && bits[][2] == 0b01001001 && bits[][3] == 0b01001100); + + bits <<= 4; + assert(bits[][0] == 0b10111100 && bits[][1] == 0b10010100 + && bits[][2] == 0b10010100 && bits[][3] == 0b11000000); + + bits <<= 8; + assert(bits[][0] == 0b10010100 && bits[][1] == 0b10010100 + && bits[][2] == 0b11000000 && bits[][3] == 0b00000000); + + bits <<= 7; + assert(bits[][0] == 0b01001010 && bits[][1] == 0b01100000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + + bits <<= 25; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + + arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101]; + bits <<= 24; + assert(bits[][0] == 0b01010101 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + + arr[1] = 0b11001100; + arr[2] = 0b11111111; + arr[3] = 0b01010101; + bits <<= 12; + assert(bits[][0] == 0b11001111 && bits[][1] == 0b11110101 + && bits[][2] == 0b01010000 && bits[][3] == 0b00000000); + + bits <<= 100; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + + arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011]; + bits >>= 0; + assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010 + && bits[][2] == 0b01010010 && bits[][3] == 0b01010011); + + bits >>= 2; + assert(bits[][0] == 0b00101111 && bits[][1] == 0b10111100 + && bits[][2] == 0b10010100 && bits[][3] == 0b10010100); + + bits >>= 4; + assert(bits[][0] == 0b00000010 && bits[][1] == 0b11111011 + && bits[][2] == 0b11001001 && bits[][3] == 0b01001001); + + bits >>= 8; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000010 + && bits[][2] == 0b11111011 && bits[][3] == 0b11001001); + + bits >>= 7; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000101 && bits[][3] == 0b11110111); + + bits >>= 25; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + + arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101]; + bits >>= 24; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00110011); + + arr[1] = 0b11001100; + arr[2] = 0b11111111; + arr[3] = 0b01010101; + bits >>= 12; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00001100 && bits[][3] == 0b11001111); + + bits >>= 100; + assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000 + && bits[][2] == 0b00000000 && bits[][3] == 0b00000000); + } + + /** + * Negates all bits. + * + * Returns: $(D_KEYWORD this). + */ + BitVector opUnary(string op)() pure nothrow @safe @nogc + if (op == "~") + { + foreach (ref b; vector) + { + b = ~b; + } + return this; + } + + /// + unittest + { + // [01000001, 00001101, 10101101] + ubyte[3] arr = [65, 13, 173]; + auto bits = BitVector(arr); + + ~bits; + assert(bits[][0] == 0b10111110); + assert(bits[][1] == 0b11110010); + assert(bits[][2] == 0b01010010); + } + + /** + * Iterates through all bits. + * + * Params: + * dg = $(D_KEYWORD foreach) delegate. + * + * Returns: By $(D_PARAM dg) returned value. + */ + int opApply(int delegate(size_t, bool) dg) + { + int result; + foreach (i, ref v; vector) + { + foreach (c; 0..8) + { + result = dg(i * 8 + c, (v & (0x80 >> c)) != 0); + if (result) + { + return result; + } + } + } + return result; + } + + /// Ditto. + int opApply(int delegate(bool) dg) + { + int result; + foreach (ref v; vector) + { + foreach (c; 0..8) + { + result = dg((v & (0x80 >> c)) != 0); + if (result) + { + return result; + } + } + } + return result; + } + + /// + unittest + { + ubyte[2] arr = [0b01000001, 0b00001101]; + auto bits = BitVector(arr); + size_t c; + + foreach (i, v; bits) + { + assert(i == c); + if (i == 1 || i == 7 || i == 15 || i == 13 || i == 12) + { + assert(v); + } + else + { + assert(!v); + } + ++c; + } + assert(c == 16); + } +} diff --git a/source/tanya/crypto/des.d b/source/tanya/crypto/des.d index a67ba6f..8154056 100644 --- a/source/tanya/crypto/des.d +++ b/source/tanya/crypto/des.d @@ -10,7 +10,7 @@ */ module tanya.crypto.des; -import tanya.container.bit; +import tanya.crypto.bit; import tanya.crypto.symmetric; /// Initial permutation table. diff --git a/source/tanya/crypto/package.d b/source/tanya/crypto/package.d index 314d0f1..37cb3c7 100644 --- a/source/tanya/crypto/package.d +++ b/source/tanya/crypto/package.d @@ -10,9 +10,7 @@ */ module tanya.crypto; -public -{ - import tanya.crypto.des; - import tanya.crypto.mode; - import tanya.crypto.symmetric; -} +public import tanya.crypto.bit; +public import tanya.crypto.des; +public import tanya.crypto.mode; +public import tanya.crypto.symmetric; diff --git a/source/tanya/memory/allocator.d b/source/tanya/memory/allocator.d index c9b7386..4da32c8 100644 --- a/source/tanya/memory/allocator.d +++ b/source/tanya/memory/allocator.d @@ -54,15 +54,30 @@ interface Allocator /** * The mixin generates common methods for classes and structs using - * allocators. It provides a protected member and a read-only property, - * that checks if an allocator was already set and sets it to the default - * one, if not (useful for structs which don't have a default constructor). + * allocators. It provides a protected member, constructor and a read-only + * property, that checks if an allocator was already set and sets it to the + * default one, if not (useful for structs which don't have a default + * constructor). */ mixin template DefaultAllocator() { /// Allocator. protected shared Allocator allocator_; + /** + * Params: + * allocator = The allocator should be used. + */ + this(shared Allocator allocator) + in + { + assert(allocator !is null); + } + body + { + this.allocator_ = allocator; + } + /** * This property checks if the allocator was set in the constructor * and sets it to the default one, if not. -- cgit v1.2.3