Inside Macintosh: Operating System Utilities /
Chapter 3 - Mathematical and Logical Utilities

# Using the Mathematical and Logical Utilities

This section describes how you can take advantage of the Mathematical and Logical Utilities supported by the Operating System, it describes how you can

• test and set individual bits, perform logical operations on long words, divide a long word into its high word and low word, and set memory values directly.
• use the `PackBits` and `UnpackBits` procedures to compress and decompress data.
• seed the pseudo-random number generator and obtain random integers or long integers within a given range.
• perform simple calculations involving fixed-point numbers and convert fixed-point numbers to other numeric types.

## Performing Low-Level Manipulation of Memory

The Mathematical and Logical Utilities provide several routines to perform bit-level and byte-level manipulation of memory. These routines are provided primarily for Pascal programmers. C and assembly-language programmers can use these routines also; however, in general it is easier and more efficient to achieve the same effects as these routines by using built-in C or assembly constructs.

### Testing and Manipulating Bits

The `BitTst` function lets you test whether a given bit is set. The function requires that you specify a bit through an offset from a pointer. Listing 3-1 is an example of an application-defined function that tests a specified bit.

Listing 3-1 Testing bits

```FUNCTION MyTestBit (bytePtr: Ptr; bitNum: LongInt): Boolean;
BEGIN
MyTestBit := BitTst(bytePtr, bitNum);
END;
```
The `bytePtr` parameter specifies a pointer to a byte in memory. The `bitNum` parameter specifies the number of the bit to be tested as an offset from `bytePtr`. For example, you can use the application-defined function `MyTestBit` to test specific bits of the word specified in Figure 3-8.

Figure 3-8 A sample word (in MC680x0 notation)

Using the word in Figure 3-8, the call `BitTst(myPtr, 0)` returns `FALSE` because bit number 0 in the first byte is not set. But the call `BitTst(myPtr, 11)` returns `TRUE` because bit number 3 in the second byte is set.

When using the `BitTst` function, be sure to specify bits as positive offsets from the high-order bit rather than using the normal MC680x0 notation (see "Reversed Bit-Numbering" on page 3-7). Listing 3-2 illustrates a use of the `BitTst` function in conjunction with a bit traditionally identified with MC680x0 notation.

Listing 3-2 Determining whether a handle is purgeable using the `BitTst` function

```FUNCTION MyHandleIsPurgeable (myHandle: Handle): Boolean;
CONST
kMyBitNum68000 = 6;
VAR
propertiesByte: SignedByte;
BEGIN
propertiesByte := HGetState(myHandle);
MyHandleIsPurgeable := BitTst(@propertiesByte,
7 - kMyBitNum68000);
END;
```
The `MyHandleIsPurgeable` function defined in Listing 3-2 determines whether a handle references a relocatable block by examining the properties byte for that handle. The purgeable bit is, in MC680x0 notation, bit number 6 of the properties byte; because `BitTst` uses reverse numbering, so bit number 7 - 6 = 1 is tested.

The `BitSet` and `BitClr` procedures require that you specify bits using the same scheme as with the `BitTst` procedure (see "Reversed Bit-Numbering" on page 3-7). The `BitSet` procedure sets a bit (that is, sets its value to 1), while `BitClr` clears a bit (that is, sets its value to 0). For example, if you issue the following two calls to the `BitSet` procedure

```BitSet(bytePtr, 5);
BitClr(bytePtr, 7);
```
bit 5 (using the reversed bit-numbering scheme) of the byte in memory pointed to by the `bytePtr` parameter is set to 1, and bit 7 (using reversed bit-numbering) of the same byte is cleared.

Note
In C, you can test bits by using the `&` operator. You can set and clear bits by using the `|=` and `&=` operators, respectively. In all three cases, one operand should be the byte (or word or long word you wish to manipulate), and the other should be a value in which only the relevant bit is set or cleared. Many Pascal compilers also support built-in operations that accomplish these tasks efficiently. Note that C uses the MC680x0 bit-numbering scheme (normal bit-numbering).

### Performing Logical Operations on Long Words

The Macintosh Operating System provides routines that allow you to perform basic bitwise logical operations, including the `AND`, `OR`, and `XOR` operations on long words. Each of the functions takes two long integers as parameters and returns another long integer. You can use these functions on other 32-bit data types, as long as you cast values to `LongInt` as required by your compiler. The functions that perform the `AND`, `OR`, and `XOR` operations are `BitAnd`, `BitOr`, and `BitXor` respectively. Figure 3-9 illustrates these functions.

Figure 3-9 The `BitAnd`, `BitOr`, and `BitXor` functions

As shown in Figure 3-9, the `BitAnd` function returns a long word in which each bit is set if and only if the corresponding bit is set in both long words passed in. The `BitOr` function returns a long word in which each bit is set if and only if the corresponding bit is set in either long word passed in. The `BitXor` function returns a long word in which each bit is set if and only if one but not both of the corresponding bits in the long words passed in is set.

Note
In C, you can achieve the same effects as the `BitAnd`, `BitOr`, and `BitXor` functions by using the `&`, `|`, and `^` operators, respectively, in conjunction with the `=` assignment operator. Many Pascal compilers also support built-in operations that accomplish these tasks more efficiently.
A common use of the `BitAnd` function is to mask out certain bytes within a long word (that is, clear all bits in those bytes). For example, to mask out the second byte of a long word stored in a variable `value`, you could write the following code:

```value := BitAnd(value, \$FF00FFFF);
```
The Macintosh Operating System also offers two bit-manipulation routines that simulate unary operators, the `BitNot` and the `BitShift` functions, which perform the `NOT` operation and bit-shifting, respectively. You specify the long integer on which to perform the operation as a parameter to the `BitNot` and `BitShift` functions. In addition, you specify how to shift the bits as a parameter to the `BitShift` function.

Figure 3-10 illustrates `BitNot` and `BitShift`.

Figure 3-10 The `BitNot` and `BitShift` functions

As shown in Figure 3-10, the `BitNot` function returns a long word in which each bit is set if and only if the corresponding bit in the long word passed in is not set. The `BitShift` function shifts bits--to the left if the `count` parameter is greater than 0 and to the right if the `count` parameter is less than 0. (Shifting to the left means shifting towards the high-order bit.) When shifting `count` bits to the left, the `count` low-order bits are set to 0; when shifting `count` bits to the right, the `count` high-order bits are set to 0.

Note
In C, you can achieve the same effect as the `BitNot` function more efficiently by using the `^` operator on the value whose bits are to be inverted and the value \$FFFFFFFF. You can achieve the same effect as the `BitShift` function more efficiently by using the `>>` operator for shifting to the right and the `<<` operator for shifting to the left. Many Pascal compilers support built-in operations that accomplish these tasks efficiently.

### Extracting a Word From a Long Word

Often a long word stored as a variable of type `LongInt` is used to hold two different pieces of information in its two different words. For example, when a disk-inserted event occurs, the `message` field of the event record contains the drive number in the low-order word and a result code in the high-order word. To access these two types of information, you can use the `HiWord` and `LoWord` functions. For example:

```VAR
x: LongInt;
high, low: Integer;
high := HiWord(x);
low := LoWord(x);
```
The `HiWord` function returns the high-order word of the long word passed in, and the `LoWord` function returns the low-order word of the long word passed in. You can use these functions with types other than `LongInt` and `Integer`, as long as they are 4 bytes and 2 bytes, respectively, and, if you are using Pascal, you cast the quantities to the correct types.

The Operating System does not provide any routines that allow you to set the high-order or low-order words of a long integer. It might seem that you could set the low-order word by calling the `BitAnd` function with the original long integer and the low-order word as parameters, and set the high-order word by calling `BitAnd` with the original long integer and the high-order word shifted left 16 bytes as parameters. The problem with this approach is that when you pass an integer variable to `BitAnd`, the compiler automatically casts the variable to a long integer. But for both integers and long integers, it is the leftmost byte that indicates the sign of the number. So when a negative integer is cast to a long integer, the low-order word of the long integer is not equal to the original integer.

However, you can use the Memory Manager's `BlockMove` procedure to directly copy the bytes of a word to the high-order or low-order word of a long word. See Inside Macintosh: Memory for more information. Or, if you wish to set both the high-order word and the low-order word of a long integer at once, you can define the following type:

```TYPE MyLongWordType =
PACKED RECORD
myHiWord:      Integer;       {high-order word}
myLoWord:      Integer;       {low-order word}
END;
```
Then you can define a variable of this type and set the high-word and low-word fields. By casting a long integer to `MyLongWordType`, you could also extract a word from a long word more efficiently than you can using the `HiWord` and `LoWord` functions.

### Hardcoding Byte Values

Occasionally, you might need to set a group of bytes in memory to specific hexadecimal values. For example, suppose your application uses a data structure with a 16-byte flags field and you wish to initialize each of the bytes in the flags field to particular values. While there are a number of ways that you might do this, the `StuffHex` procedure provides a simple, though usually inefficient, option.

You provide a pointer to any data structure in memory, and a string of hexadecimal digits as parameters to the `StuffHex` procedure. For example:

```StuffHex(@x, 'D34E0F29');
```
Of course, it would in this case be just as easy--and more efficient--to write the following code:

```x := \$D34E0F29;
```
The `StuffHex` procedure is perhaps most useful when you wish to assign a large or odd number of bytes or set the values of particular bytes within a variable. For example, to set the low-order word of a long integer `x` to \$64B5, you could use the following code:

```StuffHex(Ptr(ORD4(@x) + 2), '64B5');
```
You could use this code rather than use the techniques described in the previous section, "Extracting a Word From a Long Word."

Note that `Ptr` and `ORD4` are used here simply to satisfy Pascal type-casting rules.

The `StuffHex` procedure might also be useful if you are developing a calculator or other application that allows users to enter hexadecimal values directly.

## Compressing Data

The `PackBits` and `UnpackBits` procedures, introduced in "Data Compression" on page 3-8, allow you to compress (or decompress) data stored in RAM. Typically, you use `PackBits` before writing data to disk and `UnpackBits` immediately after writing data from disk.

Both procedures require that you pass in the `srcPtr` and `dstPtr` parameters values that point to the beginning of the source buffer and the destination buffer, respectively. The `PackBits` procedure compresses the data in the source buffer and stores the result in the destination buffer; the `UnpackBits` procedure decompresses the data in the source buffer and stores the result in the destination buffer. You must also pass to the `PackBits` procedure and the `UnpackBits` procedure a value that specifies the size of the original, uncompressed data. Because you must pass this information to `UnpackBits`, you typically use these procedures only to compress a data structure with a fixed size, so that this size can be passed as a parameter to `PackBits`.

Your application is responsible for allocating memory for both the source and the destination buffers. When `PackBits` and `UnpackBits` complete operation, the `srcPtr` and `dstPtr` parameter are incremented so that `srcPtr` points to the memory immediately following the source bytes, and `dstPtr` points to the data immediately following the destination bytes. This feature was originally designed to allow you to pack large buffers of data at once in chunks, although `PackBits` can automatically chunk large data buffers in versions of system software 6.0.2 and later. In any case, your application must store copies of `srcPtr` and `dstPtr` to access the start of the source or destination buffer after calling `PackBits` or `UnpackBits`.

One use of the compression routines might be to compress resources in your application's resource fork. Many types of resources can be made significantly smaller by compression. Listing 3-3 shows how you can pack data stored in a handle to a specified resource.

Listing 3-3 Packing data to a resource

```PROCEDURE MyAddPackedResource (srcData: Handle; theType: ResType;
theID: Integer; name: Str255);
VAR
srcBytes:         Integer;                {bytes of unpacked data}
maxDstBytes:      LongInt;                {maximum length of packed data}
dstData:          Handle;                 {packed data}
srcPtr:           Ptr;                    {pointer to unpacked data}
dstPtr:           Ptr;                    {pointer to packed data}
srcProperties:    SignedByte;             {properties of source handle}
BEGIN
srcBytes := GetHandleSize(srcData);       {find size of source}
{calculate maximum possible }
{ size of packed data}
maxDstBytes := srcBytes + (srcBytes + 126) DIV 127;
dstData := NewHandle(maxDstBytes + 2);    {allocate memory for source, }
{ plus length info}
IF dstData <> NIL THEN                    {check for NIL handle}
BEGIN
BlockMove(@srcBytes, dstData^, 2);     {copy source into buffer}
srcPtr := srcData^;                    {copy source pointer}
dstPtr := Ptr(ORD4(dstData^) + 2);     {copy destination pointer}
PackBits(srcPtr, dstPtr, srcBytes);    {pack source to destination}
{shrink destination data}
SetHandleSize(dstData, ORD4(dstPtr) - ORD4(dstData^));
srcProperties := HGetState(srcData);   {get source handle properties}
IF BitTst(@srcProperties, 2) THEN      {is source a real resource?}
RemoveResource(srcData);            {remove current resource}
WriteResource(dstData);                {write resource data}
DetachResource(dstData);               {detach from resource map}
DisposeHandle(dstData);                {dispose of destination data}
END;
END;
```
The `MyAddPackedResource` procedure declared in Listing 3-3 initially allocates a destination buffer to hold compressed data that is big enough to hold the compressed data in a worst-case scenario, plus 2 bytes to store information at the beginning of the resource about the size of the source data. Because `PackBits` does not move memory, the handle storing the destination buffer does not need to be locked. However, to prevent the `PackBits` procedure from changing the value of a master pointer, you should only pass copies of the dereferenced handle to the procedure. After `PackBits` returns, `MyAddPackedResource` determines how much memory the compressed data takes up by computing how much the `dstPtr` variable has changed. `MyAddPackedResource` then resizes the handle containing the compressed data to the appropriate size. Finally, `MyAddPackedResource` writes the new resource, after first removing the existing resource if the source handle is a handle to a resource. For more information on resources, see Inside Macintosh: More Macintosh Toolbox.

Having used the `MyAddPackedResource` procedure to compress resource data, your application needs to be able read the resource and decompress it using the `UnpackBits` procedure. Listing 3-4 shows how you might accomplish this.

Listing 3-4 Decompressing data from a packed resource

```FUNCTION MyGetPackedResource (theType: ResType; theID: Integer): Handle;
VAR
srcData:          Handle;                    {handle to packed data}
dstData:          Handle;                    {handle to unpacked data}
srcPtr:           Ptr;                       {pointer to packed data}
dstPtr:           Ptr;                       {pointer to unpacked data}
dstBytes:         Integer;                   {number of unpacked bytes}
BEGIN
srcData := GetResource(theType, theID);      {get the resource}
BlockMove(srcData^, @dstBytes, 2);           {read number of bytes of }
{ unpacked data}
dstData := NewHandle(dstBytes);              {allocate memory for }
{ unpacked data}
IF dstData <> NIL THEN
BEGIN
srcPtr := Ptr(ORD4(srcData^) + 2);        {copy source pointer}
dstPtr := dstData^;                       {copy destination pointer}
UnpackBits(srcPtr, dstPtr, dstBytes);     {unpack source to }
{ destination}
END;
IF srcData <> NIL THEN                       {if there was a resource}
BEGIN
DetachResource(srcData);                  {detach from resource map}
DisposeHandle(srcData);                   {dispose the resource}
END;
MyGetPackedResource := dstData;              {return destination handle}
END;
```
The `MyGetPackedResource` function reads in a resource that has previously been packed, determines the size of the unpacked data by copying the first 2 bytes of the resource data, and allocates a relocatable block of this size. The remainder of the data is unpacked using the `UnpackBits` procedure, and the original packed resource data is disposed of.

## Obtaining Pseudorandom Numbers

The `Random` function makes it easy to obtain pseudorandom numbers. Before you use `Random`, however, you should seed the pseudo-random number generator. Listing 3-5 shows a common technique for doing this.

Listing 3-5 Seeding the pseudo-random number generator

```PROCEDURE MySeedGenerator;
BEGIN
GetDateTime(randSeed);
END;
```
The `MySeedGenerator` procedure defined in Listing 3-5 simply uses the Date and Time Utilities' `GetDateTime` procedure to copy the number of seconds since midnight, January 1, 1904, to the global variable `randSeed`. You might use some other volatile long-word value--such as the mouse location--to seed the pseudo-random number generator, or you might even take a word from one source and a word from another. However, just using `GetDateTime` is sufficient for most applications.

Sometimes you wish to obtain a pseudo-random integer from a large range of integers; for example, you might need a pseudo-random integer in the range of -20,000 to 20,000. Listing 3-6 shows how you might do this.

Listing 3-6
A simple way of obtaining a large random integer from a range
of pseudo-random numbers

```FUNCTION MyRandomLargeRange (min, max: Integer): Integer;
VAR
randInt:       Integer;
BEGIN
REPEAT
randInt := Random
UNTIL (randInt >= min) AND (randInt <= max);
MyRandomLargeRange := randInt;
END;
```
The MyRandomLargeRange function defined in Listing 3-6 simply calls the `Random` function until it returns an acceptable value. This approach is efficient when you need a random integer from a range of integers that is wide, though not quite as wide as the range the `Random` function returns by default. However, if you need a random number from a small range--for example, a random number from 1 to 10--the MyRandomLargeRange function is inefficient. Listing 3-7 shows an alternative approach.

Listing 3-7 Obtaining a pseudo random integer from a small range of numbers

```FUNCTION MyRandomRange (min, max: Integer): Integer;
CONST
kMinRand = -32767.0;
kMaxRand = 32767.0;
VAR
myRand:     Integer;
x:          Real;          {Random scaled to [0..1]}
BEGIN
{find random number, and scale it to [0.0..1.0]}
x := (Random - kMinRand) / (kMaxRand + 1.0 - kMinRand);
{scale x to [min, max + 1.0], truncate, and return result}
MyRandomRange := TRUNC(x * (max + 1.0 - min) + min);
END;
```
The `MyRandomRange` function defined in Listing 3-7 first scales the integral value returned by the `Random` function to a floating-point value from 0 up to, but not including, 1. The function then scales the result to a real number greater than or equal to `min` but less than `max + 1`. By truncating extra decimal places, the correct result is achieved. Note that to force the compiler to perform floating-point calculations, all constants in the function are expressed as real numbers rather than as integers.

Sometimes an application might require a pseudo-random long integer. Listing 3-8 shows how you can do this.

Listing 3-8 Obtaining a pseudo-random long integer

```FUNCTION MyRandomLongInt: LongInt;
TYPE
MyLongWordType = PACKED RECORD
myHiWord:   Integer;             {high-order word}
myLoWord:   Integer;             {low-order word}
END;
VAR
myLongWord:    MyLongWordType;      {random long word}
BEGIN
{obtain random high-order word}
myLongWord.myHiWord := Random;
{obtain random low-order word}
myLongWord.myLoWord := Random;
{cast and return result}
MyRandomLongInt := LongInt(myLongWord);
END;
```
The `MyRandomLongInt` function defined in Listing 3-8 uses a technique discussed in "Extracting a Word From a Long Word" on page 3-18 to stuff a pseudo-random number in the high-order word of a long integer and another pseudo-random number in the low-order word of the long integer. If you need to obtain a long integer within a specified range, you can define routines analogous to Listing 3-6 and Listing 3-7 but use the `MyRandomLongInt` function in place of the `Random` function.

## Using Fixed-Point Data Types

Most high-level language compilers include built-in support for the `Fixed` and `Fract` data types so that you can perform regular mathematical operations with fixed-point variables. Also, the algorithms for performing addition and subtraction on `Fixed` and `Fract` variables are the same as the algorithms for performing such operations on variables of type `LongInt`.

The Operating System, however, includes several routines that allow you to convert `Fixed` and `Fract` variables to other formats, including SANE's `Extended` data type, and allow you to perform some simple operations on `Fixed` and `Fract` variables. If you need more sophisticated numeric functions, consult the Apple Numerics Manual.

To perform multiplication and division of fixed-point numbers, you can use the `FixMul`, `FixDiv`, `FracMul`, and `FracDiv` functions, which allow you to multiply `Fixed` point numbers with each other or with other long integers.

You can multiply and divide 32-bit quantities of different types using these functions. The format of the result in this case depends on the particular function being used. See descriptions of the individual functions in "Multiplying and Dividing Fixed-Point Numbers" beginning on page 3-38 for more information.

Using the `FracSqrt`, `FracCos`, `FracSin`, and `FixATan2` functions, you can perform a few special arithmetic operations involving variables of type `Fixed` and `Fract`.

The `FracSqrt` function allows you to obtain the square root of a variable of type `Fract`, interpreting bit 0 as having weight 2 rather than -2. The `FracCos` and `FracSin` provide support for the trigonometric cosine and sine functions. The `FixATan2` function provides support for the arctangent function. The arguments to all of these functions should be expressed in radians, not in degrees.

Note
To provide fast trigonometric approximations, these trigonometric functions use values of Pi correct only to 4 decimal places. You should thus use alternative SANE routines when you require better precision.
To convert among 32-bit numeric types, you can use the `Long2Fix`, `Fix2Long`, `Fix2Frac`, and `Frac2Fix` functions.

Each of the functions returns its parameter converted into the appropriate format.

You can also convert fixed-point values to and from the SANE `Extended` floating-point type using the `Fix2X`, `X2Fix`, `Frac2X`, and `X2Frac` functions.

Two additional functions, `FixRatio` and `FixRound`, allow you to perform special conversions on variables of type `Fixed`.

The `FixRatio` function returns the fixed-point quotient of the `numer` and `denom` parameters. The `FixRound` function rounds a variable of type `Fixed` to the nearest integer. If the value is halfway between two integers (0.5), it is rounded to the integer with the higher absolute value. To round a negative fixed-point number, negate it, round it, and then negate it again.

Note
To convert a variable of type `Fixed` to a variable of type `Integer` simply use the `HiWord` function to extract the integral component of the fixed-point number.
The Operating System also provides the `LongMul` procedure that allows you to multiple two 32-bit quantities and obtain a 64-bit quantity.

Table 3-2 summaries the routines that perform operations on the `Fixed` and `Fract` data types.

Table 3-2 Routines for fixed-point data types
RoutineDescription
FixMulMultiply a variable of type `Fixed` with another variable of type `Fixed` or with a variable of type `Fract` or `LongInt`
FixDivDivide two variables of the same type (`Fixed`, `Fract`, or `LongInt`) or divide a `LongInt` or `Fract` number by a `Fixed` number
FracMulMultiply a variable of type `Fract` with another variable of type `Fract` or with a variable of type `Fixed` or `LongInt`
FracDivDivide two variables of the same type (`Fixed`, `Fract`, or `LongInt`) or divide a `LongInt` or `Fixed` number by a `Fract` number
FracSqrtCompute the square root of a variable of type `Fract`
FracCosObtain the cosine of a variable of type `Fixed`
FracSinObtain the sine of a variable of type `Fixed`
FixATan2Obtain the arctangent of a variable of type `Fixed, Fract`, or `LongInt`
Long2FixConvert a variable of type `LongInt` to `Fixed`
Fix2LongConvert a variable of type `Fixed` to `LongInt`
Fix2FracConvert a variable of type `Fixed` to `Fract`
Frac2FixConvert a variable of type `Fract` to `Fixed`
Fix2XConvert a variable of type `Fixed` to `Extended`
X2FixConvert a variable of type `Extended` to `Fixed`
Frac2XConvert a variable of type `Fract` to `Extended`
X2FracConvert a variable of type `Extended` to `Fract`
FixRatioObtain the `Fixed` equivalent of a fraction
FixRoundRound a fixed-point number to the nearest integer
LongMulMultiply two 32-bit quantities and obtain a 64-bit quantity