lib/mlton/basic/word.sml

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006, 2008 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  *
   5  * MLton is released under a BSD-style license.
   6  * See the file MLton-LICENSE for details.
   7  *)
   8
   9 structure Word:
  10    sig
  11       include WORD
  12
  13       val addCheck: t * t -> t (* may raise Overflow *)
  14       val fromWord8: Word8.t -> t
  15       (* fromWord8s f.  f 0 should return the least significant byte
  16        * and f 3 should return the most significant.
  17        *)
  18       val fromWord8s: (int -> Word8.t) -> t
  19       val log2: t -> t (* 2 ^ (log2 w) <= w < 2 ^ (1 + log2 w) *)
  20       val maxPow2ThatDivides: t -> word
  21       val toWord8: t -> Word8.t
  22       (* val rotateLeft: t * t -> t *)
  23       val roundDownToPowerOfTwo: t -> t
  24       val roundUpToPowerOfTwo: t -> t
  25    end =
  26    struct
  27       structure Int = Pervasive.Int
  28       open Pervasive.Word
  29       structure Z = FixWord (Pervasive.Word)
  30       open Z
  31
  32       val equals: t * t -> bool = op =
  33
  34       fun fromWord8s (f: int -> Word8.t): t =
  35          let
  36             fun g (i, shift) =
  37                Pervasive.Word.<< (Word8.toWord (f i), shift)
  38             fun loop (w, i, shift) =
  39                if Int.>= (Int.* (i, 8), Pervasive.Word.wordSize)
  40                   then w
  41                else loop (orb (w, g (i, shift)),
  42                           Int.+ (i, 1),
  43                           shift + 0w8)
  44          in
  45             loop (0w0, 0, 0w0)
  46          end
  47
  48       val fromWord = fn x => x
  49       val toWord = fn x => x
  50       val toWordX = fn x => x
  51
  52       val fromIntInf = fromLargeInt
  53       val toIntInf = toLargeInt
  54       val toIntInfX = toLargeIntX
  55
  56       val fromWord8 = Word8.toWord
  57       val toWord8 = Word8.fromWord
  58
  59       fun log2 (w: t): t =
  60          if w = 0w0
  61             then Error.bug "Word.log2: 0"
  62          else
  63             let
  64                fun loop (n, s, ac): word =
  65                   if n = 0w1
  66                      then ac
  67                   else
  68                      let
  69                         val (n, ac) =
  70                            if n >= << (0w1, s)
  71                               then (>> (n, s), ac + s)
  72                            else (n, ac)
  73                      in
  74                         loop (n, >> (s, 0w1), ac)
  75                      end
  76             in
  77                loop (w, 0w16, 0w0)
  78             end
  79
  80       fun roundDownToPowerOfTwo (w: t) = << (0w1, log2 w)
  81
  82       fun roundUpToPowerOfTwo w =
  83          let
  84             val w' = roundDownToPowerOfTwo w
  85          in
  86             if w = w'
  87                then w
  88             else w' * 0w2
  89          end
  90
  91       structure M = MaxPow2ThatDivides (open Word
  92                                         type t = word
  93                                         val equals: t * t -> bool = op =
  94                                         val one: t = 0w1
  95                                         val zero: t = 0w0)
  96       open M
  97
  98       fun addCheck (w, w') =
  99          if w <= ~ 0w1 - w'
 100             then w + w'
 101          else raise Overflow
 102    end