Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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 |