Additional `Word` operations

[Skyb0rg007]

Description

Many algorithms require fast implementations of binary operations. For example, Haskell's implementation of big-endian patricia trees (Data.IntMap) uses countLeadingZeros internally.

Because SML/NJ has two different word sizes (31 for 32-bit, 63 for 64-bit), it is very useful to provide optimal implementations specialized to the particular system. Additionally, exposing these operations allows them to be implemented even more efficiently through the future LLVM backend.

popCount, countLeadingZeros, and countTrailingZeros all have clear uses. log2 could be a useful variant of countLeadingZeros which mirrors the function available to IntInf. While I do not currently know any use for rotl or rotr, MLton provides these functions as primitives, and they would be good to add for compatibility's sake.

MLton does also provide bswap : word -> word, which swaps bytes in the word. This does not seem easy to implement in the WORD signature, since 63-bit words don't have an obvious notion of byte swapping. Perhaps this could be considered for Word32 and Word64, or as an addition to Unsafe.Word32 or Unsafe.Word64 if a use-case is found.

signature WORD_EXTRAS =
sig
  type word
  (* Number of set bits in the input. Already implemented in SML/NJ. *)
  val popCount : word -> int

  (* Count number of zero bits preceding the most significant set bit. *)
  val countLeadingZeros : word -> int

  (* Count number of zero bits following the least significant set bit. *)
  val countTrailingZeros : word -> int

  (* The log base 2 of the input
     log2 w = Word.fromInt wordSize - 1 - countLeadingZeros w *)
  val log2 : word -> int

  (* Rotate the input to the left or right by the specified amount.
     rotl (w, s) = (w << s) orb (w >> (wordSize - s))
     rotr (w, s) = (w >> s) orb (w << (wordSize - s)) *)
  val rotl : word * Word.word -> word
  val rotr : word * Word.word -> word
end