strmantle.nim 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  1. #
  2. #
  3. # Nim's Runtime Library
  4. # (c) Copyright 2018 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. # Compilerprocs for strings that do not depend on the string implementation.
  10. import std/private/digitsutils
  11. proc cmpStrings(a, b: string): int {.inline, compilerproc.} =
  12. let alen = a.len
  13. let blen = b.len
  14. let minlen = min(alen, blen)
  15. if minlen > 0:
  16. result = c_memcmp(unsafeAddr a[0], unsafeAddr b[0], cast[csize_t](minlen)).int
  17. if result == 0:
  18. result = alen - blen
  19. else:
  20. result = alen - blen
  21. proc leStrings(a, b: string): bool {.inline, compilerproc.} =
  22. # required by upcoming backends (NIR).
  23. cmpStrings(a, b) <= 0
  24. proc ltStrings(a, b: string): bool {.inline, compilerproc.} =
  25. # required by upcoming backends (NIR).
  26. cmpStrings(a, b) < 0
  27. proc eqStrings(a, b: string): bool {.inline, compilerproc.} =
  28. result = false
  29. let alen = a.len
  30. let blen = b.len
  31. if alen == blen:
  32. if alen == 0: return true
  33. return equalMem(unsafeAddr(a[0]), unsafeAddr(b[0]), alen)
  34. proc hashString(s: string): int {.compilerproc.} =
  35. # the compiler needs exactly the same hash function!
  36. # this used to be used for efficient generation of string case statements
  37. var h = 0'u
  38. for i in 0..len(s)-1:
  39. h = h + uint(s[i])
  40. h = h + h shl 10
  41. h = h xor (h shr 6)
  42. h = h + h shl 3
  43. h = h xor (h shr 11)
  44. h = h + h shl 15
  45. result = cast[int](h)
  46. proc eqCstrings(a, b: cstring): bool {.inline, compilerproc.} =
  47. if pointer(a) == pointer(b): result = true
  48. elif a.isNil or b.isNil: result = false
  49. else: result = c_strcmp(a, b) == 0
  50. proc hashCstring(s: cstring): int {.compilerproc.} =
  51. # the compiler needs exactly the same hash function!
  52. # this used to be used for efficient generation of cstring case statements
  53. if s.isNil: return 0
  54. var h : uint = 0
  55. var i = 0
  56. while true:
  57. let c = s[i]
  58. if c == '\0': break
  59. h = h + uint(c)
  60. h = h + h shl 10
  61. h = h xor (h shr 6)
  62. inc i
  63. h = h + h shl 3
  64. h = h xor (h shr 11)
  65. h = h + h shl 15
  66. result = cast[int](h)
  67. proc c_strtod(buf: cstring, endptr: ptr cstring): float64 {.
  68. importc: "strtod", header: "<stdlib.h>", noSideEffect.}
  69. const
  70. IdentChars = {'a'..'z', 'A'..'Z', '0'..'9', '_'}
  71. powtens = [1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
  72. 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
  73. 1e20, 1e21, 1e22]
  74. {.push staticBoundChecks: off.}
  75. proc nimParseBiggestFloat(s: openArray[char], number: var BiggestFloat,
  76. ): int {.compilerproc.} =
  77. # This routine attempt to parse float that can parsed quickly.
  78. # i.e. whose integer part can fit inside a 53bits integer.
  79. # their real exponent must also be <= 22. If the float doesn't follow
  80. # these restrictions, transform the float into this form:
  81. # INTEGER * 10 ^ exponent and leave the work to standard `strtod()`.
  82. # This avoid the problems of decimal character portability.
  83. # see: https://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/
  84. var
  85. i = 0
  86. sign = 1.0
  87. kdigits, fdigits = 0
  88. exponent = 0
  89. integer = uint64(0)
  90. fracExponent = 0
  91. expSign = 1
  92. firstDigit = -1
  93. hasSign = false
  94. # Sign?
  95. if i < s.len and (s[i] == '+' or s[i] == '-'):
  96. hasSign = true
  97. if s[i] == '-':
  98. sign = -1.0
  99. inc(i)
  100. # NaN?
  101. if i+2 < s.len and (s[i] == 'N' or s[i] == 'n'):
  102. if s[i+1] == 'A' or s[i+1] == 'a':
  103. if s[i+2] == 'N' or s[i+2] == 'n':
  104. if i+3 >= s.len or s[i+3] notin IdentChars:
  105. number = NaN
  106. return i+3
  107. return 0
  108. # Inf?
  109. if i+2 < s.len and (s[i] == 'I' or s[i] == 'i'):
  110. if s[i+1] == 'N' or s[i+1] == 'n':
  111. if s[i+2] == 'F' or s[i+2] == 'f':
  112. if i+3 >= s.len or s[i+3] notin IdentChars:
  113. number = Inf*sign
  114. return i+3
  115. return 0
  116. if i < s.len and s[i] in {'0'..'9'}:
  117. firstDigit = (s[i].ord - '0'.ord)
  118. # Integer part?
  119. while i < s.len and s[i] in {'0'..'9'}:
  120. inc(kdigits)
  121. integer = integer * 10'u64 + (s[i].ord - '0'.ord).uint64
  122. inc(i)
  123. while i < s.len and s[i] == '_': inc(i)
  124. # Fractional part?
  125. if i < s.len and s[i] == '.':
  126. inc(i)
  127. # if no integer part, Skip leading zeros
  128. if kdigits <= 0:
  129. while i < s.len and s[i] == '0':
  130. inc(fracExponent)
  131. inc(i)
  132. while i < s.len and s[i] == '_': inc(i)
  133. if firstDigit == -1 and i < s.len and s[i] in {'0'..'9'}:
  134. firstDigit = (s[i].ord - '0'.ord)
  135. # get fractional part
  136. while i < s.len and s[i] in {'0'..'9'}:
  137. inc(fdigits)
  138. inc(fracExponent)
  139. integer = integer * 10'u64 + (s[i].ord - '0'.ord).uint64
  140. inc(i)
  141. while i < s.len and s[i] == '_': inc(i)
  142. # if has no digits: return error
  143. if kdigits + fdigits <= 0 and
  144. (i == 0 or # no char consumed (empty string).
  145. (i == 1 and hasSign)): # or only '+' or '-
  146. return 0
  147. if i+1 < s.len and s[i] in {'e', 'E'}:
  148. inc(i)
  149. if s[i] == '+' or s[i] == '-':
  150. if s[i] == '-':
  151. expSign = -1
  152. inc(i)
  153. if s[i] notin {'0'..'9'}:
  154. return 0
  155. while i < s.len and s[i] in {'0'..'9'}:
  156. exponent = exponent * 10 + (ord(s[i]) - ord('0'))
  157. inc(i)
  158. while i < s.len and s[i] == '_': inc(i) # underscores are allowed and ignored
  159. var realExponent = expSign*exponent - fracExponent
  160. let expNegative = realExponent < 0
  161. var absExponent = abs(realExponent)
  162. # if exponent greater than can be represented: +/- zero or infinity
  163. if absExponent > 999:
  164. if integer == 0:
  165. number = 0.0
  166. elif expNegative:
  167. number = 0.0*sign
  168. else:
  169. number = Inf*sign
  170. return i
  171. # if integer is representable in 53 bits: fast path
  172. # max fast path integer is 1<<53 - 1 or 8999999999999999 (16 digits)
  173. let digits = kdigits + fdigits
  174. if digits <= 15 or (digits <= 16 and firstDigit <= 8):
  175. # max float power of ten with set bits above the 53th bit is 10^22
  176. if absExponent <= 22:
  177. if expNegative:
  178. number = sign * integer.float / powtens[absExponent]
  179. else:
  180. number = sign * integer.float * powtens[absExponent]
  181. return i
  182. # if exponent is greater try to fit extra exponent above 22 by multiplying
  183. # integer part is there is space left.
  184. let slop = 15 - kdigits - fdigits
  185. if absExponent <= 22 + slop and not expNegative:
  186. number = sign * integer.float * powtens[slop] * powtens[absExponent-slop]
  187. return i
  188. # if failed: slow path with strtod.
  189. var t: array[500, char] # flaviu says: 325 is the longest reasonable literal
  190. var ti = 0
  191. let maxlen = t.high - "e+000".len # reserve enough space for exponent
  192. let endPos = i
  193. result = endPos
  194. i = 0
  195. # re-parse without error checking, any error should be handled by the code above.
  196. if i < endPos and s[i] == '.': i.inc
  197. while i < endPos and s[i] in {'0'..'9','+','-'}:
  198. if ti < maxlen:
  199. t[ti] = s[i]; inc(ti)
  200. inc(i)
  201. while i < endPos and s[i] in {'.', '_'}: # skip underscore and decimal point
  202. inc(i)
  203. # insert exponent
  204. t[ti] = 'E'
  205. inc(ti)
  206. t[ti] = if expNegative: '-' else: '+'
  207. inc(ti, 4)
  208. # insert adjusted exponent
  209. t[ti-1] = ('0'.ord + absExponent mod 10).char
  210. absExponent = absExponent div 10
  211. t[ti-2] = ('0'.ord + absExponent mod 10).char
  212. absExponent = absExponent div 10
  213. t[ti-3] = ('0'.ord + absExponent mod 10).char
  214. number = c_strtod(cast[cstring](addr t), nil)
  215. {.pop.} # staticBoundChecks
  216. proc nimBoolToStr(x: bool): string {.compilerRtl.} =
  217. return if x: "true" else: "false"
  218. proc nimCharToStr(x: char): string {.compilerRtl.} =
  219. result = newString(1)
  220. result[0] = x
  221. when defined(gcDestructors):
  222. proc GC_getStatistics*(): string =
  223. result = "[GC] total memory: "
  224. result.addInt getTotalMem()
  225. result.add "\n[GC] occupied memory: "
  226. result.addInt getOccupiedMem()
  227. result.add '\n'
  228. #"[GC] cycle collections: " & $gch.stat.cycleCollections & "\n" &