1 LISP LIBRARY PACKAGES MANUAL 1 LISP LIBRARY PACKAGES MANUAL CMLFLOATARRAY 1 COMMON LISP 1 CMLFLOATARRAY 6 The CMLFloatArray package implements high-speed vector operations and various array functions using them. Though CMLFloatArray takes advantage of the special capabilities of the Xerox 1108X, it can be run on any of the machines in the 1100 series. The package includes functions for one- and two-dimensional FFTs, matrix multiplication and transposition, as well as general functions to map n-ary operations onto the elements of a set of matrices. CMLFloatArray uses the Common Lisp array package (CMLArray) and will load it if not already loaded. Warning: Complex format arrays (described below) must be quadword aligned. To create a quadword aligned array use the :ALIGNMENT 64 keyword argument to MAKE-ARRAY. Warning: Arrays given as arguments to the FFT functions (described below) must be page aligned. To create a page aligned array use the :PAGE-ALIGN T keyword argument to MAKE-ARRAY 2 Mapping Operations 1 MAPARRAY is a general vectorizing function. It is capable of handling arrays of any dimensions and will in most cases create a result array of the correct dimensions if one is not supplied by the caller. E.g., a call to MAPARRAY with two arrays and one scalar as arguments, and the function MAX as mapfn, will create a result array with the same dimensions as the array arguments (they have to be equal), containing the maximum value of the three arguments. (MAPARRAY RESULT MAPFN ARRAY1 ARRAY2. . . ARRAYN) [Function] MAPARRAY will set RESULT[i,j] to the value returned by applying MAPFN to ARRAY1[i,j], ARRAY2[i,j]. . . , ARRAYN[i,j] for all [i,j]. If RESULT is NIL then an appropriate-sized array is created to hold the result. Returns RESULT. MAPFN can be an arbitrary n-ary Lisp function. MAPARRAY deals with cases of one or two input arrays specially, deferring to the functions MAPARRAY1 and MAPARRAY2. MAPARRAY is much faster than an equivalent function written in Lisp. We use ┅SMALLP构 for an array of type (UNSIGNED-BYTE 16) and ┅FLOAT构 for an array of type SINGLE-FLOAT. A ┅COMPLEX构 array is an array of type FLOAT whose successive pairs of elements are considered the real and imaginary parts of a complex number. Thus, if C is a complex array, then the nth complex number of C, C[n], has real part (AREF C ... (ITIMES 2 n)) and imaginary part (AREF C . . . (ADD1 (ITIMES 2 n))). (MAPARRAY1 RESULT MAPFN ARRAY) [Function] Applies MAPARRAY1 to each element of ARRAY, and places the result in the corresponding element of RESULT. MAPFN can be any unary function or one of a group of distinguished pseudo-functions, each of which is realized using a microcoded operation on the 1108X. EXPONENT Sets SMALLP RESULT[n] to the EXPONENT field of FLOATP ARRAY[n]. EXPONENT can be used as a fast logarithm to base two converter. The result is the eight high bits of the 32-bit floating point number. The exponent of 0.0 is 0. 0.0625 has the exponent 123, and 8.0 has the exponent 130. FLOAT Sets FLOAT RESULT[n] to SMALLP ARRAY[n]. I.e., a smallp-to-floating point vectorized conversion routine. COMPLEX Sets COMPLEX RESULT[n] to FLOAT ARRAY[n]. If ARRAY[n] is a, then RESULT[n] is a+0.0i. See the complex array alignment warning at the beginning of this document. MAGNITUDE Sets FLOAT RESULT[n] to the square of the magnitude of the complex number ARRAY[n]. E.g., if one really wants the magnitude of a vector one can write: (MAPARRAY NIL 'SQRT (MAPARRAY NIL 'MAGNITUDE ARRAY)) This is somewhat inefficient as we create one temporary array containing the squared magnitudes. (MAPARRAY2 RESULT MAPFN ARRAY1 ARRAY2) [Function] Applies MAPFN to the corresponding elements of ARRAY1 and ARRAY2, placing the results in RESULT. MAPFN can be any binary Lisp function, though the following pseudo-functions are specially recognized and run in microcode on an 1108X. FPLUS Sets FLOAT RESULT[n] to the sum of ARRAY1[n] and ARRAY2[n]. If either of ARRAY1 or ARRAY2 is a number, it is first converted to an array of the same dimensions as the other array. I.e., to add 1.0 to each element in the array WEIGHTS one could write: (MAPARRAY WEIGHTS (FUNCTION FPLUS) WEIGHTS 1.0) Warning: If WEIGHTS were a large array this would be very inefficient as an array is generated to hold the numeric value. See ADDARR for a more efficient way to add scalars to an array. FDIFF Sets FLOAT RESULT[n] to FDIFFERENCE of FLOAT ARRAY1[n] and FLOAT ARRAY2[n]. Numeric arguments are treated as in FPLUS. FTIMES Sets FLOAT RESULT[n] to FTIMES of FLOAT ARRAY1[n] and FLOAT ARRAY2[n]. As in FPLUS and FDIFF, numeric arguments are converted to arrays before applying the operation. PERMUTE This function does not type check the arguments RESULT and ARRAY1. It permutates the array ARRAY1 through ARRAY2, storing data in RESULT. All data transfers are done by word (16-bit quantities). ARRAY2 has to be a one-dimensional array with element type (UNSIGNED-BYTE 16). Example 1 Suppose we want to transpose a three-by-three-element array Q. Then we precalculate the permutation vector PERMQ: PERMQ = #( 0 1 6 7 12 13 2 3 8 9 14 15 4 5 10 11 16 17). To calculate the actual transposition we could then write: (SETQ QT (MAPARRAY NIL 'PERMUTE Q PERMQ)). Note: We cannot have RESULT = ARRAY1 here. 2 Fast Fourier Transforms 1 The CMLFloatArray package contains functions to calculate the FFT of one- and two-dimensional vectors. These operations are highly optimized and largely implemented in microcode (on the 1108X). Please read the FFT array argument alignment warning at thebeginning of this document. One-Dimensional FFT 1 (FFT ARRAY STARTPOSITION LENGTH INVERSFLAG \BASEPTR) [Function] Calculates the FFT of a one-dimensional array (EQ (ARRAY-RANK ARRAY) 1) and stores the result in the same array. ARRAY must be a complex array and page aligned (see warning at beginning of document). The result is, of course, complex. STARTPOSITION is the first element in ARRAY to be used in the FFT calculation (defaulting to zero). LENGTH is the number of complex elements to be used in the FFT calculation. LENGTH must be a power of two. LENGTH defaults to the size of the array. If INVERSEFLAG is non-NIL the inverse FFT is calculated. The last argument, \BASEPTR, is primarily for internal use. It is a pointer to a block of floating-point numbers. Two-Dimensional FFT 1 (2DFFT ARRAY INVERSEFLAG) [Function] Calculates the two-dimensional FFT of an an array. ARRAY is a complex array with dimensions m * (2n) where both m and n must be a power of two. ARRAY must be page aligned (see warning at beginning of document). If INVERSEFLAG is non-NIL then the inverse transformation is calculated. Typical calculation times: size (1D) time size (2D) time n = 256 14 ms n = 128 * 128 3.8 s n = 512 22 ms n = 256 * 256 13.5 s n = 1024 41 ms 2 Other 2D Matrix Operations 1 (2DCTIMES ARRAY1 ARRAY2 RESULT) [Function] This function sets RESULT[i,j] to ARRAY1[i,j] * ARRAY2[i,j] where * represents complex multiplication. RESULT, ARRAY1 and ARRAY2 should be complex arrays and quadword aligned (see warning at beginning of document). If RESULT is NIL the result is stored in ARRAY1, i.e., pointwise multiply. (2DTRANS ARRAY RESULT) [Function] Transposes an array of floating-point numbers. Returns RESULT. If ARRAY has dimensions n*m then RESULT should have the dimensions m*n. If RESULT is NIL an array is created to hold the result. If ARRAY=RESULT and n=m then the transposition is done in place. (2DMMUL XARRAY YARRAY ZARRAY) [Function] This is the standard matrix multiplication algorithm. It sets ZARRAY[i,j] to the sum of XARRAY[i,k] * YARRAY[k,j] where k= 0..p-1 if XARRAY has dimensions n*p, YARRAY p*m, and ZARRAY n*m. If ZARRAY is NIL then a new array is created to hold the result. Returns ZARRAY. Arrays and Scalars 1 The functions described below have all microcode support on an 1108X and are very fast. As an example, adding or multiplying a scalar and a 128-by-256-element array takes approximately 0.13 sec. (ADDARR ARRAY X) [Macro] Adds the scalar X to each element in ARRAY. The array can be any array of element type FLOAT (and overall data type ARRAY). Returns NIL. (SUBARR ARRAY X) [Macro] Implemented as (ADDARR ARRAY (FMINUS X)). (MULARR ARRAY X) [Macro] Multiplies each element in ARRAY by X. Returns NIL. (DIVARR ARRAY X) [Macro] Implemented as (MULARR ARRAY (FQUOTIENT 1.0 X)). Minimum and Maximum 1 These operations come in two flavors, one that ignores the sign (magnitude compare) and one that uses it. The operations work as reductions, i.e., find the maximum element in the array. There are two classes of operations, depending on what kind of result is wanted. The first class returns the value of the element and the second returns an index to it. All operations separate the case of a complex array argument. If such an array is given, the operation uses the IMFLAG to determine which part to examine (real or imaginary). (MINARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the minimum element. (MINABSARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the minimum absolute value element. (MAXARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the maximum element. (MAXABSARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the maximum absolute value element. (WHERE-MINARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the index of the minimum element. (WHERE-MINABSARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the index of the minimum absolute value element. (WHERE-MAXARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the index of the maximum element. (WHERE-MAXABSARR ARRAY COMPLEXFLG IMFLG) [Function] Returns the index of the maximum absolute value element. Conversions 1 The conversion functions described below have one major drawback; they are mainly concerned with eight-bit-per-pixel bit maps. Further, for the sake of absolute speed, the ┅to bit map构 conversions require that the source arrays have row length evenly divisible by two (or by four for complex arrays). All functions below have either microcode support or are written with efficient use of existing operations (such as BITBLT). (BITMAP-TO-COMPLEX BM ARRAY) [Function] Converts a one-, four-, or eight-bit-per-pixel bit map to a complex array (imaginary part set to zero). ARRAY is created if not supplied. Returns ARRAY. (BITMAP-TO-FLOAT BM ARRAY) [Function] Converts a one-, four-, or eight-bit-per-pixel bit map to a float array . ARRAY is created if not supplied. Returns ARRAY. (COMPLEX-TO-BITMAP ARRAY BM IMFLG) [Function] Converts a complex array to a bit map. ARRAY must have rows with a length evenly divisible by four. The real part is used if IMFLG is NIL, otherwise the imaginary part. A bit map (BM) is created if not supplied. If an array element is greater than 255 or less than zero it is limited to that number. Returns BM. (FLOAT-TO-BITMAP ARRAY BM) [Function] Converts a float array into a bit map using the same limiting described above. As above, ARRAY must have rows with a length evenly divisible by four. A bit map (BM) is created if not supplied. Returns BM. (FLOAT-TO-COMPLEX RE IM ARRAY) [Function] Packs two arrays into one, assuming that one array provides the real part and the other the imaginary part. ARRAY is created if not supplied. Returns ARRAY. (COMPLEX-TO-FLOAT CARRAY FARRAY IMFLG) [Function] Separates either the real or imaginary part of a complex array into a float array. FARRAY is created if not supplied. Returns FARRAY. FFT of Real 2D Matrices 1 If we are working with real matrices (e.g., bit maps) there is a way to save a lot of work (and space) by combining two raw arrays into one. Call the first raw array X and the second Y, then let Z = X + iY, i.e., put the components of the first raw array in the ┅real slot构 and the second raw array in the ┅imaginary slot.构 After taking the FFT of Z it is fairly easy to separate the result into two parts because the fourier transform of a real vector has symmetric (odd and even) real and imaginary parts. Functions that work on the presumption that data is stored in this way have an ┅X构 in their names (e.g., 2DXFFT, 2DCXTIMES, BITMAP-TO-XCOMPLEX and XCOMPLEX-TO-BITMAP). (2DXFFT MAT INVFLG) [Function] Calculates the FFT transform of a matrix (MAT) under the assumption that data is stored as described above. The operation is done in place similar to the complex 2DFFT operation. The format of the result is described above. Returns NIL. (2DCXTIMES M1 M2 M3) [Function] Does pointwise multiplication of two matrices under the assumption that they are fourier transforms calculated by 2DXFFT. If M3 is NIL then the result is stored back into M1. (BITMAP-TO-XCOMPLEX BM ARRAY) [Function] Converts a bit map, BM, to a complex array. Data is packed as described above. ARRAY is created if not supplied. Returns ARRAY. (XCOMPLEX-TO-BITMAP ARRAY BM) [Function] Converts a complex array into a bit map. Limiting is done as described in the function COMPLEX-TO-BITMAP. As in COMPLEX-TO-BITMAP, ARRAY must have rows with a length evenly divisible by four. Returns BM. Miscellaneous 1 (POLYNOM X COEFF DEGREE) [Function] This function calculates the value of a polynomial at the point X. The polynomial is described by the coefficients and the degree. E.g., POLYNOM is used to implement the SIN, COS, and LOG functions in Interlisp. COEFF should be a one-dimensional array of element type float and DEGREE, an integer. (SUMARR ARRAY COMPLEXFLG IMFLG) [Function] Calculates the sum of the components in ARRAY. If COMPLEXFLG is non-NIL the sum of the real part is calculated, otherwise, the imaginary part. Returns the sum. 2 Warning for Users of the 1108X 1 A batch of delivered floating-point chips have been found to contain a bug. The bug occurs when two small numbers are multiplied and the result is an unnormalized number. The chip generates floating infinity as the result. The function CHIPTEST, supplied in the CMLFloatArray package, can be used to test if this bug is present in your 1108X. If your machine has this problem, please contact your Xerox sales representative for information on how to obtain either a replacement chip or service. This bug does not occur in the function FTIMES, as the chip is used in ┅slow mode构 in that function. (LIST ((PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC) STARTINGPAGE# 360) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD LEFT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (54 12 288 36) NIL) (HEADING NIL (HEADINGTYPE FOOTINGV) (54 27 558 36) NIL) (HEADING NIL (HEADINGTYPE VERSOHEAD) (54 762 558 36) NIL) (TEXT NIL NIL (54 54 504 618) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD RIGHT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (270 12 288 36) NIL) (HEADING NIL (HEADINGTYPE FOOTINGR) (54 27 558 36) NIL) (HEADING NIL (HEADINGTYPE RECTOHEAD) (54 762 558 36) NIL) (TEXT NIL NIL (54 54 504 684) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD LEFT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (54 12 288 36) NIL) (HEADING NIL (HEADINGTYPE FOOTINGV) (54 27 558 36) NIL) (HEADING NIL (HEADINGTYPE VERSOHEAD) (54 762 558 36) NIL) (TEXT NIL NIL (54 54 504 684) NIL)))))./T)T22T2T72n724H.=,D\t)T.. )2T)T(( )T)TB PAGEHEADING VERSOHEADB PAGEHEADING RECTOHEADA PAGEHEADINGFOOTINGVA PAGEHEADINGFOOTINGR. MODERNMODERNTERMINAL MODERN  HELVETICA MODERN MODERN MODERN MODERN  HRULE.GETFNMODERN    HRULE.GETFNMODERN     HRULE.GETFNMODERN    HRULE.GETFNMODERN   HRULE.GETFNMODERN  d    HRULE.GETFNMODERN HRULE.GETFNMODERN       (     P       % 8     $     F      [   9 H 5 a    "            0      2     g  0     = J   HRULE.GETFNMODERN ? 3    = +    HRULE.GETFNMODERN HRULE.GETFNMODERN X   HRULE.GETFNMODERN      q v  9 F  ( ? X   HRULE.GETFNMODERN      3 Y B ;   $ %   HRULE.GETFNMODERN HRULE.GETFNMODERN        3   [       8   % 4   $       >       B    HRULE.GETFNMODERN W l       _      *              1   HRULE.GETFNMODERN  9              ,            ,        *        9        *        9   HRULE.GETFNMODERN        i &        J &         ( R 3         Z D '         m &         T &    HRULE.GETFNMODERN       *        ~ ,         ; &        A    HRULE.GETFNMODERN       B  >         (  e  HRULE.GETFNMODERN  HRULE.GETFNMODERN[  8_z