lib/mlton/basic/max-pow-2-that-divides.fun

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 2004-2006 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 functor MaxPow2ThatDivides (type t
  10
  11                             val << : t * word -> t
  12                             val >> : t * word -> t
  13                             val <= : t * t -> bool
  14                             val andb: t * t -> t
  15                             val equals: t * t -> bool
  16                             val one: t
  17                             val orb: t * t -> t
  18                             val zero: t):
  19    sig
  20       val maxPow2ThatDivides: t -> word
  21    end =
  22    struct
  23       structure Word = Pervasive.Word
  24
  25       val maxPow2ThatDivides: t -> word =
  26          fn i =>
  27          let
  28             (* b is the number of zero bits we are trying to peel from the
  29              *   bottom of i.
  30              * m = 2^b - 1.  m is a mask for the bits we are trying to peel.
  31              * 0 < a <= m.
  32              * ac is the number of bits that we have already peeled off.
  33              *)
  34             fun down (b: word, m: t, i: t, ac: word): word =
  35                let
  36                   val b = Word.>> (b, 0w1)
  37                in
  38                   if b = 0w0
  39                      then ac
  40                   else
  41                      let
  42                         val m = >> (m, b)
  43                         val a = andb (i, m)
  44                         val (i, ac) =
  45                            if equals (a, zero)
  46                               then (>> (i, b), ac + b)
  47                            else (a, ac)
  48                      in
  49                         down (b, m, i, ac)
  50                      end
  51                end
  52             fun up (b: word, m: t): word =
  53                let
  54                   val a = andb (i, m)
  55                in
  56                   if equals (a, zero)
  57                      then up (Word.<< (b, 0w1), orb (m, << (m, b)))
  58                   else down (b, m, a, 0w0)
  59                end
  60          in
  61             if i <= zero
  62                then Error.bug "MaxPow2ThatDivides.maxPow2ThatDivides: i <= 0"
  63             else up (0w1, one)
  64          end
  65    end