More numeric host-level operations

[o-santi]

One of the most used operations in the SHA3 family of hash functions is U64.RotateLeft (specifically used a lot in the Keccak-F1600 function). In my implementation, it is used exactly 348 times inside the F function. In CPU terms, this is a very cheap operation, and should only take a few clock cycles (on most modern CPU's, just 1), but there's no native operator for it, which made me need to write the following function:

!(ROL64 arg0 arg1) {
  !(ROL64 a n) =
     &{n.0 n.1} = n;
     &{a.0 a.1} = a;
 (% (+ (>> a.0 (- #64 (% n.0 #64))) (<< a.1 (% n.1 #64))) (<< #1 #64))
} = #0

This function costs 11 rewrites (220 mana) every time it is called, and considering it is called 348 times per F call, ROL64 by itself takes up most of the cost of the computation. Were there an operator for it, it would only take 1 (and it would even be optimized at the assembly level). This would make the hash function much much cheaper to compute (roughly about 8~10 times fewer rewrites), since F is called multiple times each time a hash is taken.

Are there any possibilities of implementing new native operations in the language, like rotate left, rotate right and so on?

[VictorTaelin]

Yes, I think we should add more operations. But which ones? What criterium should we adopt? Perhaps about ~24 operations on U120, U64, U32, U16, U8, I120, I64, I32, I16, I8? Aiming for 256 operations (1 byte) total?

[steinerkelvin]

Proposal: xTUP values having the bigger numbers on the least significant bits, so the 64-bit numbers – which I hope will be the most used – never need a shift left to be operated on.

_________________________________________________________________________________________________________________________
|  TAG  |  U8   |      U16      |              U32              |                              U64                      |
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

[steinerkelvin]

Proposal: "get byte"/"set byte" operations, so we can operate efficiently on arbitraty indexes of byte-arrays implemented on trees of Nums.

[VictorTaelin]

I approve both ideas above. Can you implement, since you've last modified the primitive operations?

Also get-byte and set-byte opcode should have index 128, since it is universal for all integer types. It would be weird to have a copy for each of the 4 types. Indices 128-255 are reserved for these kinds of functions.

[steinerkelvin]

I'll do it.

[steinerkelvin]

Lower-sized number operations were removed from the current version.

@o-santi Do you think it's still useful to have at least some operations on U64?

I believe there should be feasible ways for users to implement conventional cryptography even if sub-optimally.

Also, actual cryptographic primitives. Like exposing Keccak and secp256k1 (on which we already depend anyway).

All of these would benefit from operations to handle bytes and "arrays".

Having arrays also gives us a more generic types to bridge with othe networks.

related to #116