diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/pure/collections/tables.nim | 6 | ||||
| -rw-r--r-- | lib/pure/random.nim | 125 | ||||
| -rw-r--r-- | lib/pure/securehash.nim | 195 | ||||
| -rw-r--r-- | lib/system.nim | 2 |
4 files changed, 102 insertions, 226 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 38f8f97f5..01767956e 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -994,7 +994,7 @@ proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## returns the (key,val)-pair with the smallest `val`. Efficiency: O(n) assert t.len > 0 var minIdx = -1 - for h in 1..high(t.data): + for h in 0..high(t.data): if t.data[h].val > 0 and (minIdx == -1 or t.data[minIdx].val > t.data[h].val): minIdx = h result.key = t.data[minIdx].key @@ -1332,5 +1332,5 @@ when isMainModule: block: # CountTable.smallest var t = initCountTable[int]() - for v in items([4, 4, 5, 5, 5]): t.inc(v) - doAssert t.smallest == (4, 2) + for v in items([0, 0, 5, 5, 5]): t.inc(v) + doAssert t.smallest == (0, 2) diff --git a/lib/pure/random.nim b/lib/pure/random.nim index e6a9162c5..7edd93c08 100644 --- a/lib/pure/random.nim +++ b/lib/pure/random.nim @@ -7,16 +7,16 @@ # distribution, for details about the copyright. # -## Nim's standard random number generator. Based on the ``xoroshiro128+`` (xor/rotate/shift/rotate) library. +## Nim's standard random number generator. Based on +## the ``xoroshiro128+`` (xor/rotate/shift/rotate) library. ## * More information: http://xoroshiro.di.unimi.it/ ## * C implementation: http://xoroshiro.di.unimi.it/xoroshiro128plus.c ## -## Do not use this module for cryptographic use! +## **Do not use this module for cryptographic purposes!** include "system/inclrtl" {.push debugger:off.} -# XXX Expose RandomGenState when defined(JS): type ui = uint32 @@ -27,31 +27,34 @@ else: const randMax = 18_446_744_073_709_551_615u64 type - RandomGenState = object + Rand* = object ## State of the random number generator. + ## The procs that use the default state + ## are **not** thread-safe! a0, a1: ui when defined(JS): - var state = RandomGenState( + var state = Rand( a0: 0x69B4C98Cu32, a1: 0xFED1DD30u32) # global for backwards compatibility else: # racy for multi-threading but good enough for now: - var state = RandomGenState( + var state = Rand( a0: 0x69B4C98CB8530805u64, a1: 0xFED1DD3004688D67CAu64) # global for backwards compatibility proc rotl(x, k: ui): ui = result = (x shl k) or (x shr (ui(64) - k)) -proc next(s: var RandomGenState): uint64 = - let s0 = s.a0 - var s1 = s.a1 +proc next*(r: var Rand): uint64 = + ## Uses the state to compute a new ``uint64`` random number. + let s0 = r.a0 + var s1 = r.a1 result = s0 + s1 s1 = s1 xor s0 - s.a0 = rotl(s0, 55) xor s1 xor (s1 shl 14) # a, b - s.a1 = rotl(s1, 36) # c + r.a0 = rotl(s0, 55) xor s1 xor (s1 shl 14) # a, b + r.a1 = rotl(s1, 36) # c -proc skipRandomNumbers(s: var RandomGenState) = +proc skipRandomNumbers*(s: var Rand) = ## This is the jump function for the generator. It is equivalent ## to 2^64 calls to next(); it can be used to generate 2^64 ## non-overlapping subsequences for parallel computations. @@ -71,21 +74,23 @@ proc skipRandomNumbers(s: var RandomGenState) = s.a0 = s0 s.a1 = s1 -proc random*(max: int): int {.benign.} = +proc random*(max: int): int {.benign, deprecated.} = ## Returns a random number in the range 0..max-1. The sequence of ## random number is always the same, unless `randomize` is called ## which initializes the random number generator with a "random" - ## number, i.e. a tickcount. + ## number, i.e. a tickcount. **Deprecated since version 0.18.0**. + ## Use ``rand`` instead. while true: let x = next(state) if x < randMax - (randMax mod ui(max)): return int(x mod uint64(max)) -proc random*(max: float): float {.benign.} = +proc random*(max: float): float {.benign, deprecated.} = ## Returns a random number in the range 0..<max. The sequence of ## random number is always the same, unless `randomize` is called ## which initializes the random number generator with a "random" - ## number, i.e. a tickcount. + ## number, i.e. a tickcount. **Deprecated since version 0.18.0**. + ## Use ``rand`` instead. let x = next(state) when defined(JS): result = (float(x) / float(high(uint32))) * max @@ -93,26 +98,92 @@ proc random*(max: float): float {.benign.} = let u = (0x3FFu64 shl 52u64) or (x shr 12u64) result = (cast[float](u) - 1.0) * max -proc random*[T](x: HSlice[T, T]): T = +proc random*[T](x: HSlice[T, T]): T {.deprecated.} = ## For a slice `a .. b` returns a value in the range `a .. b-1`. + ## **Deprecated since version 0.18.0**. + ## Use ``rand`` instead. result = T(random(x.b - x.a)) + x.a -proc random*[T](a: openArray[T]): T = +proc random*[T](a: openArray[T]): T {.deprecated.} = ## returns a random element from the openarray `a`. + ## **Deprecated since version 0.18.0**. + ## Use ``rand`` instead. result = a[random(a.low..a.len)] +proc rand*(r: var Rand; max: int): int {.benign.} = + ## Returns a random number in the range 0..max. The sequence of + ## random number is always the same, unless `randomize` is called + ## which initializes the random number generator with a "random" + ## number, i.e. a tickcount. + while true: + let x = next(r) + if x <= randMax - (randMax mod ui(max)): + return int(x mod (uint64(max)+1u64)) + +proc rand*(max: int): int {.benign.} = + ## Returns a random number in the range 0..max. The sequence of + ## random number is always the same, unless `randomize` is called + ## which initializes the random number generator with a "random" + ## number, i.e. a tickcount. + rand(state, max) + +proc rand*(r: var Rand; max: float): float {.benign.} = + ## Returns a random number in the range 0..max. The sequence of + ## random number is always the same, unless `randomize` is called + ## which initializes the random number generator with a "random" + ## number, i.e. a tickcount. + let x = next(r) + when defined(JS): + result = (float(x) / float(high(uint32))) * max + else: + let u = (0x3FFu64 shl 52u64) or (x shr 12u64) + result = (cast[float](u) - 1.0) * max + +proc rand*(max: float): float {.benign.} = + ## Returns a random number in the range 0..max. The sequence of + ## random number is always the same, unless `randomize` is called + ## which initializes the random number generator with a "random" + ## number, i.e. a tickcount. + rand(state, max) + +proc rand*[T](r: var Rand; x: HSlice[T, T]): T = + ## For a slice `a .. b` returns a value in the range `a .. b`. + result = T(rand(r, x.b - x.a)) + x.a + +proc rand*[T](x: HSlice[T, T]): T = + ## For a slice `a .. b` returns a value in the range `a .. b`. + result = rand(state, x) + +proc rand*[T](r: var Rand; a: openArray[T]): T = + ## returns a random element from the openarray `a`. + result = a[rand(r, a.low..a.high)] + +proc rand*[T](a: openArray[T]): T = + ## returns a random element from the openarray `a`. + result = a[rand(a.low..a.high)] + + +proc initRand*(seed: int64): Rand = + ## Creates a new ``Rand`` state from ``seed``. + result.a0 = ui(seed shr 16) + result.a1 = ui(seed and 0xffff) + discard next(result) + proc randomize*(seed: int64) {.benign.} = - ## Initializes the random number generator with a specific seed. - state.a0 = ui(seed shr 16) - state.a1 = ui(seed and 0xffff) - discard next(state) + ## Initializes the default random number generator + ## with a specific seed. + state = initRand(seed) -proc shuffle*[T](x: var openArray[T]) = - ## Will randomly swap the positions of elements in a sequence. +proc shuffle*[T](r: var Rand; x: var openArray[T]) = + ## Swaps the positions of elements in a sequence randomly. for i in countdown(x.high, 1): - let j = random(i + 1) + let j = r.rand(i) swap(x[i], x[j]) +proc shuffle*[T](x: var openArray[T]) = + ## Swaps the positions of elements in a sequence randomly. + shuffle(state, x) + when not defined(nimscript): import times @@ -134,12 +205,12 @@ when isMainModule: var x = 8234 for i in 0..100_000: - x = random(len(occur)) # myrand(x) + x = rand(high(occur)) inc occur[x] for i, oc in occur: if oc < 69: doAssert false, "too few occurrences of " & $i - elif oc > 130: + elif oc > 150: doAssert false, "too many occurrences of " & $i var a = [0, 1] diff --git a/lib/pure/securehash.nim b/lib/pure/securehash.nim deleted file mode 100644 index 57c1f3631..000000000 --- a/lib/pure/securehash.nim +++ /dev/null @@ -1,195 +0,0 @@ -# -# -# The Nim Compiler -# (c) Copyright 2015 Nim Contributors -# -# See the file "copying.txt", included in this -# distribution, for details about the copyright. -# - -import strutils - -const Sha1DigestSize = 20 - -type - Sha1Digest = array[0 .. Sha1DigestSize-1, uint8] - SecureHash* = distinct Sha1Digest - -# Copyright (c) 2011, Micael Hildenborg -# All rights reserved. -# -# Redistribution and use in source and binary forms, with or without -# modification, are permitted provided that the following conditions are met: -# * Redistributions of source code must retain the above copyright -# notice, this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright -# notice, this list of conditions and the following disclaimer in the -# documentation and/or other materials provided with the distribution. -# * Neither the name of Micael Hildenborg nor the -# names of its contributors may be used to endorse or promote products -# derived from this software without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY Micael Hildenborg ''AS IS'' AND ANY -# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL Micael Hildenborg BE LIABLE FOR ANY -# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES -# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; -# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND -# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT -# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS -# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -# -# Ported to Nim by Erik O'Leary - -type - Sha1State* = array[0 .. 5-1, uint32] - Sha1Buffer = array[0 .. 80-1, uint32] - -template clearBuffer(w: Sha1Buffer, len = 16) = - zeroMem(addr(w), len * sizeof(uint32)) - -proc init*(result: var Sha1State) = - result[0] = 0x67452301'u32 - result[1] = 0xefcdab89'u32 - result[2] = 0x98badcfe'u32 - result[3] = 0x10325476'u32 - result[4] = 0xc3d2e1f0'u32 - -proc innerHash(state: var Sha1State, w: var Sha1Buffer) = - var - a = state[0] - b = state[1] - c = state[2] - d = state[3] - e = state[4] - - var round = 0 - - template rot(value, bits: uint32): uint32 = - (value shl bits) or (value shr (32 - bits)) - - template sha1(fun, val: uint32) = - let t = rot(a, 5) + fun + e + val + w[round] - e = d - d = c - c = rot(b, 30) - b = a - a = t - - template process(body: untyped) = - w[round] = rot(w[round - 3] xor w[round - 8] xor w[round - 14] xor w[round - 16], 1) - body - inc(round) - - template wrap(dest, value: untyped) = - let v = dest + value - dest = v - - while round < 16: - sha1((b and c) or (not b and d), 0x5a827999'u32) - inc(round) - - while round < 20: - process: - sha1((b and c) or (not b and d), 0x5a827999'u32) - - while round < 40: - process: - sha1(b xor c xor d, 0x6ed9eba1'u32) - - while round < 60: - process: - sha1((b and c) or (b and d) or (c and d), 0x8f1bbcdc'u32) - - while round < 80: - process: - sha1(b xor c xor d, 0xca62c1d6'u32) - - wrap state[0], a - wrap state[1], b - wrap state[2], c - wrap state[3], d - wrap state[4], e - -proc sha1(src: cstring; len: int): Sha1Digest = - #Initialize state - var state: Sha1State - init(state) - - #Create w buffer - var w: Sha1Buffer - - #Loop through all complete 64byte blocks. - let byteLen = len - let endOfFullBlocks = byteLen - 64 - var endCurrentBlock = 0 - var currentBlock = 0 - - while currentBlock <= endOfFullBlocks: - endCurrentBlock = currentBlock + 64 - - var i = 0 - while currentBlock < endCurrentBlock: - w[i] = uint32(src[currentBlock+3]) or - uint32(src[currentBlock+2]) shl 8'u32 or - uint32(src[currentBlock+1]) shl 16'u32 or - uint32(src[currentBlock]) shl 24'u32 - currentBlock += 4 - inc(i) - - innerHash(state, w) - - #Handle last and not full 64 byte block if existing - endCurrentBlock = byteLen - currentBlock - clearBuffer(w) - var lastBlockBytes = 0 - - while lastBlockBytes < endCurrentBlock: - - var value = uint32(src[lastBlockBytes + currentBlock]) shl - ((3'u32 - uint32(lastBlockBytes and 3)) shl 3) - - w[lastBlockBytes shr 2] = w[lastBlockBytes shr 2] or value - inc(lastBlockBytes) - - w[lastBlockBytes shr 2] = w[lastBlockBytes shr 2] or ( - 0x80'u32 shl ((3'u32 - uint32(lastBlockBytes and 3)) shl 3) - ) - - if endCurrentBlock >= 56: - innerHash(state, w) - clearBuffer(w) - - w[15] = uint32(byteLen) shl 3 - innerHash(state, w) - - # Store hash in result pointer, and make sure we get in in the correct order - # on both endian models. - for i in 0 .. Sha1DigestSize-1: - result[i] = uint8((int(state[i shr 2]) shr ((3-(i and 3)) * 8)) and 255) - -proc sha1(src: string): Sha1Digest = - ## Calculate SHA1 from input string - sha1(src, src.len) - -proc secureHash*(str: string): SecureHash = SecureHash(sha1(str)) -proc secureHashFile*(filename: string): SecureHash = secureHash(readFile(filename)) -proc `$`*(self: SecureHash): string = - result = "" - for v in Sha1Digest(self): - result.add(toHex(int(v), 2)) - -proc parseSecureHash*(hash: string): SecureHash = - for i in 0 ..< Sha1DigestSize: - Sha1Digest(result)[i] = uint8(parseHexInt(hash[i*2] & hash[i*2 + 1])) - -proc `==`*(a, b: SecureHash): bool = - # Not a constant-time comparison, but that's acceptable in this context - Sha1Digest(a) == Sha1Digest(b) - - -when isMainModule: - let hash1 = secureHash("a93tgj0p34jagp9[agjp98ajrhp9aej]") - doAssert hash1 == hash1 - doAssert parseSecureHash($hash1) == hash1 diff --git a/lib/system.nim b/lib/system.nim index e66699ae4..83e87683a 100644 --- a/lib/system.nim +++ b/lib/system.nim @@ -463,7 +463,7 @@ type line*: int ## line number of the proc that is currently executing filename*: cstring ## filename of the proc that is currently executing - Exception* {.compilerproc.} = object of RootObj ## \ + Exception* {.compilerproc, magic: "Exception".} = object of RootObj ## \ ## Base exception class. ## ## Each exception has to inherit from `Exception`. See the full `exception |