pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Lite
#
#
#            Nim's Runtime Library
#        (c) Copyright 2018 Nim contributors
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## Note this API is still experimental! A variable length integer
## encoding implementation inspired by SQLite.

const
  maxVarIntLen* = 9 ## the maximal number of bytes a varint can take

proc readVu64*(z: openArray[byte]; pResult: var uint64): int =
  if z[0] <= 240:
    pResult = z[0]
    return 1
  if z[0] <= 248:
    if z.len < 2: return 0
    pResult = (uint64 z[0] - 241) * 256 + z[1].uint64 + 240
    return 2
  if z.len < int(z[0]-246): return 0
  if z[0] == 249:
    pResult = 2288u64 + 256u64*z[1].uint64 + z[2].uint64
    return 3
  if z[0] == 250:
    pResult = (z[1].uint64 shl 16u64) + (z[2].uint64 shl 8u64) + z[3].uint64
    return 4
  let x = (z[1].uint64 shl 24) + (z[2].uint64 shl 16) + (z[3].uint64 shl 8) + z[4].uint64
  if z[0] == 251:
    pResult = x
    return 5
  if z[0] == 252:
    pResult = (((uint64)x) shl 8) + z[5].uint64
    return 6
  if z[0] == 253:
    pResult = (((uint64)x) shl 16) + (z[5].uint64 shl 8) + z[6].uint64
    return 7
  if z[0] == 254:
    pResult = (((uint64)x) shl 24) + (z[5].uint64 shl 16) + (z[6].uint64 shl 8) + z[7].uint64
    return 8
  pResult = (((uint64)x) shl 32) +
              (0xffffffff'u64 and ((z[5].uint64 shl 24) +
              (z[6].uint64 shl 16) + (z[7].uint64 shl 8) + z[8].uint64))
  return 9

proc varintWrite32(z: var openArray[byte]; y: uint32) =
  z[0] = uint8(y shr 24)
  z[1] = uint8(y shr 16)
  z[2] = uint8(y shr 8)
  z[3] = uint8(y)

proc writeVu64*(z: var openArray[byte], x: uint64): int =
  ## Write a varint into z. The buffer z must be at least 9 characters
  ## long to accommodate the largest possible varint. Returns the number of
  ## bytes used.
  if x <= 240:
    z[0] = uint8 x
    return 1
  if x <= 2287:
    let y = uint32(x - 240)
    z[0] = uint8(y shr 8 + 241)
    z[1] = uint8(y and 255)
    return 2
  if x <= 67823:
    let y = uint32(x - 2288)
    z[0] = 249
    z[1] = uint8(y shr 8)
    z[2] = uint8(y and 255)
    return 3
  let y = uint32 x
  let w = uint32(x shr 32)
  if w == 0:
    if y <= 16777215:
      z[0] = 250
      z[1] = uint8(y shr 16)
      z[2] = uint8(y shr 8)
      z[3] = uint8(y)
      return 4
    z[0] = 251
    varintWrite32(toOpenArray(z, 1, z.high-1), y)
    return 5
  if w <= 255:
    z[0] = 252
    z[1] = uint8 w
    varintWrite32(toOpenArray(z, 2, z.high-2), y)
    return 6
  if w <= 65535:
    z[0] = 253
    z[1] = uint8(w shr 8)
    z[2] = uint8 w
    varintWrite32(toOpenArray(z, 3, z.high-3), y)
    return 7
  if w <= 16777215:
    z[0] = 254
    z[1] = uint8(w shr 16)
    z[2] = uint8(w shr 8)
    z[3] = uint8 w
    varintWrite32(toOpenArray(z, 4, z.high-4), y)
    return 8
  z[0] = 255
  varintWrite32(toOpenArray(z, 1, z.high-1), w)
  varintWrite32(toOpenArray(z, 5, z.high-5), y)
  return 9

proc sar(a, b: int64): int64 =
  {.emit: [result, " = ", a, " >> ", b, ";"].}

proc sal(a, b: int64): int64 =
  {.emit: [result, " = ", a, " << ", b, ";"].}

proc encodeZigzag*(x: int64): uint64 {.inline.} =
  uint64(sal(x, 1)) xor uint64(sar(x, 63))

proc decodeZigzag*(x: uint64): int64 {.inline.} =
  let casted = cast[int64](x)
  result = (`shr`(casted, 1)) xor (-(casted and 1))

when isMainModule:
  #import random

  var dest: array[50, byte]
  var got: uint64

  for test in [0xFFFF_FFFF_FFFFF_FFFFu64, 77u64, 0u64, 10_000_000u64, uint64(high(int64)),
               uint64(high(int32)),uint64(low(int32)),uint64(low(int64))]:
    let wrLen = writeVu64(dest, test)
    let rdLen = readVu64(dest, got)
    assert wrLen == rdLen
    echo(if got == test: "YES" else: "NO")
    echo "number is ", got

    if encodeZigzag(decodeZigzag(test)) != test:
      echo "Failure for ", test, " ", encodeZigzag(decodeZigzag(test)), " ", decodeZigzag(test)

  for test in 0u64..300u64:
    let wrLen = writeVu64(dest, test)
    let rdLen = readVu64(dest, got)
    assert wrLen == rdLen
    if got != test:
      echo "BUG! expected: ", test, " got: ", got, " z0: ", dest[0]

  # check this also works for floats:
  for test in [0.0, 0.1, 2.0, +Inf, Nan, NegInf]:
    let t = cast[uint64](test)
    let wrLenB = writeVu64(dest, t)
    let rdLenB = readVu64(dest, got)
    assert wrLenB == rdLenB
    echo rdLenB
    echo(if cast[float64](got) == test: "YES" else: "NO")