The Standard ML Basis Library

The `WORD` signature

Synopsis

signature WORD structure Word :> WORD where type word = word structure Word8 :> WORD structure LargeWord :> WORD structure Word<N> :> WORD (* OPTIONAL *) structure SysWord :> WORD (* OPTIONAL *)

Instances of the signature WORD provide a type of unsigned integer with modular arithmetic and logical operations and conversion operations. They are also meant to give efficient access to the primitive machine word types of the underlying hardware, and support bit-level operations on integers. They are not meant to be a ``larger'' int.

In order to provide a more intuitive description of the shift operators below, we assume a bit ordering in which the most significant bit is leftmost, and the least significant bit is rightmost.

Interface

eqtype word val wordSize : int val toLarge : word -> LargeWord.word val toLargeX : word -> LargeWord.word val toLargeWord : word -> LargeWord.word val toLargeWordX : word -> LargeWord.word val fromLarge : LargeWord.word -> word val fromLargeWord : LargeWord.word -> word val toLargeInt : word -> LargeInt.int val toLargeIntX : word -> LargeInt.int val fromLargeInt : LargeInt.int -> word val toInt : word -> int val toIntX : word -> int val fromInt : int -> word val andb : word * word -> word val orb : word * word -> word val xorb : word * word -> word val notb : word -> word val << : word * Word.word -> word val >> : word * Word.word -> word val ~>> : word * Word.word -> word val + : word * word -> word val - : word * word -> word val * : word * word -> word val div : word * word -> word val mod : word * word -> word val compare : word * word -> order val < : word * word -> bool val <= : word * word -> bool val > : word * word -> bool val >= : word * word -> bool val ~ : word -> word val min : word * word -> word val max : word * word -> word val fmt : StringCvt.radix -> word -> string val toString : word -> string val scan : StringCvt.radix -> (char, 'a) StringCvt.reader -> (word, 'a) StringCvt.reader val fromString : string -> word option

Description

val wordSize : int

The number of bits in type word. wordSize need not be a power of two. Note that word has a fixed, finite precision.

toLarge w

toLargeX w

These convert w to a value of type LargeWord.word. In the first case, w is converted to its equivalent LargeWord.word value in the range [0,2^(wordSize)-1]. In the second case, w is ``sign-extended,'' i.e., the wordSize low-order bits of w and toLargeX w are the same, and the remaining bits of toLargeX w are all equal to the most significant bit of w.

toLargeWord and toLargeWordX are respective synonyms of the first two, and are deprecated.

fromLarge w

fromLargeWord w

These functions convert w to the value w(mod (2^(wordSize))) of type word. This has the effect of taking the low-order wordSize bits of the 2's complement representation of w.

fromLargeWord is a deprecated synonym for fromLarge.

toLargeInt w

toLargeIntX w

These convert w to a value of type LargeInt.int. In the former case, w is viewed as an integer value in the range [0,2^(wordSize)-1]. In the latter case, w is treated as a 2's complement signed integer with wordSize precision, thereby having a value in the range [-2^(wordSize-1),2^(wordSize-1)-1]. toLargeInt raises Overflow if the target integer value cannot be represented as a LargeInt.int. Since the precision of LargeInt.int is always at least wordSize (see the discussion below), toLargeIntX will never raise an exception.

fromLargeInt i

converts i of type LargeInt.int to a value of type word. This has the effect of taking the low-order wordSize bits of the 2's complement representation of i.

toInt w

toIntX w

These convert w to a value of default integer type. In the former case, w is viewed as an integer value in the range [0,2^(wordSize)-1]. In the latter case, w is treated as a 2's complement signed integer with wordSize precision, thereby having a value in the range [-2^(wordSize-1),2^(wordSize-1)-1]. They raise Overflow if the target integer value cannot be represented as an Int.int.

fromInt i

converts i of the default integer type to a value of type word. This has the effect of taking the low-order wordSize bits of the 2's complement representation of i. If the precision of Int.int is less than wordSize, then i is sign-extended to wordSize bits.

val andb : word * word -> word val orb : word * word -> word val xorb : word * word -> word

These functions return the bit-wise AND, OR, and exclusive OR, respectively, of their arguments.

notb i

returns the bit-wise complement (NOT) of i.

<< (i, n)

shifts i to the left by n bit positions, filling in zeros from the right. When i and n are interpreted as unsigned binary numbers, this returns (i* 2⁽ⁿ⁾)(mod (2 ^(wordSize))). In particular, shifting by greater than or equal to wordSize results in 0. This operation is similar to the ``(logical) shift left'' instruction in many processors.

>> (i, n)

shifts i to the right by n bit positions, filling in zeros from the left. When i and n are interpreted as unsigned binary numbers, it returns floor((i / 2⁽ⁿ⁾)). In particular, shifting by greater than or equal to wordSize results in 0. This operation is similar to the ``logical shift right'' instruction in many processors.

~>> (i, n)

shifts i to the right by n bit positions. The value of the leftmost bit of i remains the same; in a 2's-complement interpretation, this corresponds to sign extension. When i is interpreted as a wordSize-bit 2's-complement integer and n is interpreted as an unsigned binary number, it returns floor((i / 2⁽ⁿ⁾)). In particular, shifting by greater than or equal to wordSize results in either 0 or all 1's. This operation is similar to the ``arithmetic shift right'' instruction in many processors.

i + j

returns (i+j)(mod (2 ^(wordSize))) when i and j are interpreted as unsigned binary numbers. It does not raise Overflow.

i - j

returns the difference of i and j modulo (2^(wordSize)):

(2^(wordSize) + i - j)(mod (2^(wordSize)))

when i and j are interpreted as unsigned binary numbers. It does not raise Overflow.

i * j

returns the product (i*j)(mod (2^(wordSize))) when i and j are interpreted as unsigned binary numbers. It does not raise Overflow.

i div j

returns the truncated quotient of i and j, floor((i / j)), when i and j are interpreted as unsigned binary numbers. It raises Div when j = 0.

i mod j

returns the remainder of the division of i by j:

i - j * floor((i / j))

when i and j are interpreted as unsigned binary numbers. It raises Div when j = 0.

compare (i, j)

returns LESS, EQUAL, or GREATER if and only if i is less than, equal to, or greater than j, respectively, considered as unsigned binary numbers.

val < : word * word -> bool val <= : word * word -> bool val > : word * word -> bool val >= : word * word -> bool

These return true if and only if the input arguments satisfy the given relation when interpreted as unsigned binary numbers.

~ i

returns the 2's complement of i.

val min : word * word -> word val max : word * word -> word

These return the smaller (respectively, larger) of the arguments.

fmt radix i

toString i

These return a string containing a numeric representation of i. No prefix "Ow", "OwX", etc. is generated. The version using fmt creates a representation specified the given radix. The hexadecimal digits in the range [10,15] are represented by the characters #"A" through #"F". The version using toString is equivalent to fmt StringCvt.HEX i.

scan radix getc strm

fromString s

These functions scan a word from a character source. In the first version, if an unsigned number in the format denoted by radix can be parsed from a prefix of the character strm strm using the character input function getc, the expression evaluates to SOME(w,rest), where w is the value of the number parsed and rest is the remainder of the character stream. Initial whitespace is ignored. NONE is returned otherwise. It raises Overflow when a number can be parsed, but is too large to fit in type word.

The format that scan accepts depends on the radix argument. Regular expressions defining these formats are as follows:

Radix	Format
`StringCvt.BIN`	(`0w`)^?[`0`-`1`]⁺
`StringCvt.OCT`	(`0w`)^?[`0`-`7`]⁺
`StringCvt.DEC`	(`0w`)^?[`0`-`9`]⁺
`StringCvt.HEX`	(`0wx` \| `0wX` \| `0x` \| `0X`)^?[`0`-`9a`-`fA`-`F`]⁺

The fromString version returns SOME(w) if an unsigned hexadecimal number in the format (0wx | 0wX | 0x | 0X)^?[0-9a-fA-F]⁺ can be parsed from a prefix of string s, ignoring initial whitespace, where w is the value of the number parsed. NONE is returned otherwise. This function raises Overflow when a hexadecimal numeral can be parsed, but is too large to be represented by type word. It is equivalent to

	    StringCvt.scanString (scan StringCvt.HEX)

Discussion

A structure Word<N> implements N-bit words. The type LargeWord.word represents the largest word supported. We require that

LargeWord.wordSize <= LargeInt.precision

If LargeWord is not the same as Word, then there must be a structure Word<N> equal to LargeWord.

The structure SysWord is used with the optional Posix and Windows modules. The type SysWord.word is guaranteed to be large enough to hold any unsigned integral value used by the underlying system.

For words and integers of the same precision/word size, the operations fromInt and toIntX act as bit-wise identity functions. Even in this case, however, toInt will raise Overflow if the high-order bit of the word is set.

Note that operations on words, and conversions of integral types into words, never cause exceptions to arise due to lost precision.

Conversion between words and integers of any size can be handled by intermediate conversion into LargeWord.word and LargeInt.int. For example, the functions fromInt, toInt and toIntX are respectively equivalent to:

fromLargeWord o LargeWord.fromLargeInt o Int.toLarge
Int.fromLarge o LargeWord.toLargeInt   o toLargeWord
Int.fromLarge o LargeWord.toLargeIntX  o toLargeWordX

Typically, implementations will provide very efficient word operations by expanding them inline to a few machine instructions. It also is assumed that implementations will catch the idiom of converting between words and integers of differing precisions using an intermediate representation (e.g., Word32.fromLargeWord o Word8.toLargeWord) and optimize these conversions.

[ Top | Parent | Contents | Index | Root ]

Generated April 12, 2004
Last Modified May 29, 2000
Comments to John Reppy.

This document may be distributed freely over the internet as long as the copyright notice and license terms below are prominently displayed within every machine-readable copy.

Copyright © 2004 AT&T and Lucent Technologies. All rights reserved.
Permission is granted for internet users to make one paper copy for their own personal use. Further hardcopy reproduction is strictly prohibited. Permission to distribute the HTML document electronically on any medium other than the internet must be requested from the copyright holders by contacting the editors. Printed versions of the SML Basis Manual are available from Cambridge University Press. To order, please visit www.cup.org (North America) or www.cup.cam.ac.uk (outside North America).