Mirror of forum.nim-lang.org

1594 :: Bugs?

• Javi (orginal) [2015-08-30T16:52:51+02:00] view original

  Hi!

  Today I've discovered Nim and I really love it! Thanks!

  I'm coding a bit to test it but I have some problems, it seems bugs but maybe I'm doing something wrong as it's my first day with Nim.

  This is the code:

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  
  proc computeCRC32Lookup(): CRC32Array =
      const polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0 .. 255:
          var crc: uint32 = cast[uint32](i)
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][result[0][i] and 0xFF'u32]
          result[2][i] = (result[1][i] shr 8) xor result[0][result[1][i] and 0xFF'u32]
          result[3][i] = (result[2][i] shr 8) xor result[0][result[2][i] and 0xFF'u32]
          result[4][i] = (result[3][i] shr 8) xor result[0][result[3][i] and 0xFF'u32]
          result[5][i] = (result[4][i] shr 8) xor result[0][result[4][i] and 0xFF'u32]
          result[6][i] = (result[5][i] shr 8) xor result[0][result[5][i] and 0xFF'u32]
          result[7][i] = (result[6][i] shr 8) xor result[0][result[6][i] and 0xFF'u32]
  Run

  The compiler says: (7, 33) Error: cannot evaluate at compile time: computeCRC32Lookup

  Then I delete the forward declaration and write the compute function over crc32Lookup:

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array =
      const polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0 .. 255:
          var crc: uint32 = cast[uint32](i)
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][result[0][i] and 0xFF'u32]
          result[2][i] = (result[1][i] shr 8) xor result[0][result[1][i] and 0xFF'u32]
          result[3][i] = (result[2][i] shr 8) xor result[0][result[2][i] and 0xFF'u32]
          result[4][i] = (result[3][i] shr 8) xor result[0][result[3][i] and 0xFF'u32]
          result[5][i] = (result[4][i] shr 8) xor result[0][result[4][i] and 0xFF'u32]
          result[6][i] = (result[5][i] shr 8) xor result[0][result[5][i] and 0xFF'u32]
          result[7][i] = (result[6][i] shr 8) xor result[0][result[6][i] and 0xFF'u32]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  And now compiler says: (12, 54) Error: cannot convert 3988292384 to range 0..1(uint32)

  Why? I'm not defining a range for polynomial... But if I change it from const to var it works:

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array =
      var polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0 .. 255:
          var crc: uint32 = cast[uint32](i)
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][result[0][i] and 0xFF'u32]
          result[2][i] = (result[1][i] shr 8) xor result[0][result[1][i] and 0xFF'u32]
          result[3][i] = (result[2][i] shr 8) xor result[0][result[2][i] and 0xFF'u32]
          result[4][i] = (result[3][i] shr 8) xor result[0][result[3][i] and 0xFF'u32]
          result[5][i] = (result[4][i] shr 8) xor result[0][result[4][i] and 0xFF'u32]
          result[6][i] = (result[5][i] shr 8) xor result[0][result[5][i] and 0xFF'u32]
          result[7][i] = (result[6][i] shr 8) xor result[0][result[6][i] and 0xFF'u32]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  But now the compiler says: (17, 58) Error: type mismatch: got (array[0..255, uint32], range 0..255(uint32))

  OK... if I make a cast to uint32 it works... (?):

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array =
      var polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0 .. 255:
          var crc: uint32 = cast[uint32](i)
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][cast[uint32](result[0][i] and 0xFF'u32)]
          result[2][i] = (result[1][i] shr 8) xor result[0][cast[uint32](result[1][i] and 0xFF'u32)]
          result[3][i] = (result[2][i] shr 8) xor result[0][cast[uint32](result[2][i] and 0xFF'u32)]
          result[4][i] = (result[3][i] shr 8) xor result[0][cast[uint32](result[3][i] and 0xFF'u32)]
          result[5][i] = (result[4][i] shr 8) xor result[0][cast[uint32](result[4][i] and 0xFF'u32)]
          result[6][i] = (result[5][i] shr 8) xor result[0][cast[uint32](result[5][i] and 0xFF'u32)]
          result[7][i] = (result[6][i] shr 8) xor result[0][cast[uint32](result[6][i] and 0xFF'u32)]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  But now the compiler says about var crc: (9, 27) Error: VM is not allowed to 'cast'

  OK, I delete the cast and use unsigneds for the loop:

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array =
      var polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0'u32 .. 255'u32:
          var crc: uint32 = i
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][cast[uint32](result[0][i] and 0xFF'u32)]
          result[2][i] = (result[1][i] shr 8) xor result[0][cast[uint32](result[1][i] and 0xFF'u32)]
          result[3][i] = (result[2][i] shr 8) xor result[0][cast[uint32](result[2][i] and 0xFF'u32)]
          result[4][i] = (result[3][i] shr 8) xor result[0][cast[uint32](result[3][i] and 0xFF'u32)]
          result[5][i] = (result[4][i] shr 8) xor result[0][cast[uint32](result[4][i] and 0xFF'u32)]
          result[6][i] = (result[5][i] shr 8) xor result[0][cast[uint32](result[5][i] and 0xFF'u32)]
          result[7][i] = (result[6][i] shr 8) xor result[0][cast[uint32](result[6][i] and 0xFF'u32)]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  No, this is not the end... now the compiler says: (17, 59) Error: VM is not allowed to 'cast'

  OMG! I change the type of cast:

  
  import unsigned
  
  type CRC32Array = array[8, array[256, uint32]]
  
  proc computeCRC32Lookup(): CRC32Array =
      var polynomial: uint32 = 0xEDB88320'u32
      
      for i in 0'u32 .. 255'u32:
          var crc: uint32 = i
          
          for j in 0 .. 7:
              crc = (crc shr 1) xor ((crc and 1'u32) * polynomial)
          
          result[0][i] = crc
      
      for i in 0 .. 255:
          result[1][i] = (result[0][i] shr 8) xor result[0][uint32(result[0][i] and 0xFF'u32)]
          result[2][i] = (result[1][i] shr 8) xor result[0][uint32(result[1][i] and 0xFF'u32)]
          result[3][i] = (result[2][i] shr 8) xor result[0][uint32(result[2][i] and 0xFF'u32)]
          result[4][i] = (result[3][i] shr 8) xor result[0][uint32(result[3][i] and 0xFF'u32)]
          result[5][i] = (result[4][i] shr 8) xor result[0][uint32(result[4][i] and 0xFF'u32)]
          result[6][i] = (result[5][i] shr 8) xor result[0][uint32(result[5][i] and 0xFF'u32)]
          result[7][i] = (result[6][i] shr 8) xor result[0][uint32(result[6][i] and 0xFF'u32)]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  And the error this time is: (25)(12) computeCRC32Lookup(12, 54) Error: conversion from 3988292384 to [0..1] is invalid

  Ufff... Had I the bad luck of finding a bunch of bugs or am I doing a lot of things wrong???

  I'm using the latest version: 0.11.3 (2015-08-30) [MacOSX: amd64]

  Thanks!

  Cheers!

  Javi

---

• Jehan (orginal) [2015-08-30T17:57:43+02:00] view original

  This seems to be a bug that happens when the compiler "knows" that the left side of a multiplication is part of an integer range. You can either cast the value to uint32 or switch the operands. E.g.:

  crc = (crc shr 1) xor ((crc and 1).uint32 * polynomial)
  Run

  or:

  crc = (crc shr 1) xor (polynomial * (crc and 1))
  Run

  In general, life is easier if you leave the values as signed integers and use the wrap-around arithmethic operators (such as +%, *%, etc.). For example:

  import unsigned
  
  type CRC32Array = array[8, array[256, int32]]
  
  proc computeCRC32Lookup(): CRC32Array =
    var polynomial = 0xEDB88320'i32
    
    for i in 0 .. 255:
      var crc = i.int32
      
      for j in 0 .. 7:
          crc = (crc shr 1) xor ((crc and 1) *% polynomial)
      
      result[0][i] = crc
    
    for i in 0 .. 255:
      result[1][i] = (result[0][i] shr 8) xor result[0][result[0][i] and 0xFF]
      result[2][i] = (result[1][i] shr 8) xor result[0][result[1][i] and 0xFF]
      result[3][i] = (result[2][i] shr 8) xor result[0][result[2][i] and 0xFF]
      result[4][i] = (result[3][i] shr 8) xor result[0][result[3][i] and 0xFF]
      result[5][i] = (result[4][i] shr 8) xor result[0][result[4][i] and 0xFF]
      result[6][i] = (result[5][i] shr 8) xor result[0][result[5][i] and 0xFF]
      result[7][i] = (result[6][i] shr 8) xor result[0][result[6][i] and 0xFF]
  
  const crc32Lookup: CRC32Array = computeCRC32Lookup()
  Run

  You can further simplify the result[k][i] = ... parts by using a template, by the way.

  Note that shr and shl perform unsigned shifts even on signed values (interpreted in two's complement form).

  To cast between integral types, simply use normal type conversion, instead of a hard cast (which tries to reinterpret the bitpattern). For example, use uint32(i) or i.uint32 instead of cast[uint32](i). This will also verify that the conversion is valid if you try to cast to a subtype (e.g., int8(0xffff) will fail).

---

• Javi (orginal) [2015-08-30T21:20:54+02:00] view original

  OK, then I'll use signed types for bitwise operations, with these wrap-around unsigned operators that Nim has for sure this kind of code will be cleaner and less error-prone.

  Thanks Jehan! ; )

---