James A. Kuzdrall has been programming digital computers since 1960 and designing them since 1970. He is an MIT and Northeastern University graduate, and enjoys creating efficient algorithms and using computers extensively in engineering analysis and instrumentation control. He may be reached at Intrel Service Co., Box 1247, Nashua, NH 03061, (603) 883-4851.
Overview
Numeric transfers between dissimilar computers can be a vexing problem for engineers and scientists. Computers represent physical measurements by one of several binary codes that differ in length, byte order, and sometimes format. Direct binary data transfers between computers with different central processors is often impossible, forcing the use of ASCII decimal (text) equivalents.The six functions presented here offer a fast, compact, and format-independent alternative to ASCII transfers via printf and scanf conversions. Remarkably, these new system-independent C functions compile without any reference to the underlying details of the host's numeric system! You don't have to know which binary representation the host uses. The binary transfer format (two-byte integer, four-byte long integer, and four-byte floating point) requires 1/3.5 to 1/5.5 times less file space or transmission time than an equivalently precise ASCII representation.
The new functions are: fputi, fgeti, fputl, fgetl, fputf, and fgetf. Each takes two parameters, the address of the transfer data and a file (stream) pointer. All functions return a zero if successful, a nonzero integer if not. The functions accommodate transfers by modem, by network, by magnetic disk, or by tape. Any transfer facility accessible through putc and getc can be used.
The transfer functions purposely avoid C library functions that may not be supported on older K&R compilers or on stripped-down microcontroller compilers. In fact, only putc and getc are needed.
Applications
The functions are particularly useful when transferring physical measurements from a microcontroller-based laboratory instrument to a more powerful computer for analysis. For example, a 68HC11-based optical radiometer might send its 1,600-measurement scan to an 80486-class computer for a report and to a VAX computer for inclusion in a scientific analysis. Radiometric measurements have accuracies of only two to four digits, but span ten decades from least measure to full scale., The floating-point functions fputf and fgetf allow the instrument to send normal units (watts, meters) rather than risk an eventual misinterpretation of scaled integers (microwatts-per-count, nanometers-per-count). In addition, the faster and more precise binary floating-point transfer requires less than one minute of 2400 baud modem time, whereas a full precision ASCII transfer requires over five minutes.
Transfer Format
Before looking at the algorithms, consider some consequences of the transfer format choice. Nonstandard formats, such as signed-magnitude integers and exponent/signed-mantissa floating-point formats, are tempting choices because they require less processing time and code in an instrument's performance-limited microcontroller. On the other hand, the more complex but widely used twos-complement integer and IEEE-754 floating-point formats allow programmers to create fast, simple, system-specific versions of the generalized transfer functions presented here in the many systems that are known to use these formats.Numeric range is another consideration. Simple formats often don't have the numeric range that users expect from the C data types. For example, the minimum signed-magnitude integer is -32,767, whereas the commonly used twos-complement form reaches -32,768. Choosing twos-complement and IEEE-754 floating-point formats for transfer accommodates the expected range of C's common data types, albeit just the minimum range.
Error reporting is another practical consideration. Since twos-complement numbers use the whole numeric range of the transfer integer, the transferred data itself cannot report an error. Instead, fputi and fputl indicate an out-of-range or a communication error by not sending the data and returning a nonzero integer. In the absence of some independent communication, the system receiving data detects an error when it gets less data than expected. Although the floating-point format has unused codes available for errors, fputf uses the same system for consistency. The sender distinguishes transfer errors from range errors by using ferror.
Integer Transfers
The integer transfer functions of Listing 1 take care of the byte order, the length, and the binary codings allowed in C. The C standard stipulates that integers use binary codes (disallowing binary-coded decimal) so that shift operators make sense. Although twos complement is by far the most common binary coding, the algorithm accepts signed magnitude, ones complement, and possibly others. Table 1 compares twos complement, signed magnitude (popular in analog-to-digital converters), and ones complement for important numbers in the representable range.The key to format-independent integer transfer is that all three binary formats represent positive numbers the same way. If integers are resolved into a positive magnitude (absolute value) and an independent sign flag, all formats will have the same binary representation. Once the integer is separated into sign and magnitude, C's format-independent bit-logic operations convert it to the twos-complement transfer format.
Positive integers equal their magnitude, requiring only that the sign be noted. Negative integers are transformed to positive magnitudes using C's arithmetic negation — most of the time anyway. The one exception is the most negative twos-complement number in Table 1. It has no positive counterpart. The value obtained for -(-32,768) is implementation-dependent and requires special handling.
The code for fputi begins with macro definitions for MAXINT and MININT. MAXINT is always +32,767, an informal standard for K&R compilers and a requirement for Standard C compilers. MININT is one of two values:
MININT provides a way to test for twos-complement range without using -32,768 in compilers where it is out of range.
- -32,767 if limited by the host compiler to the minimum C requirement
- -32,768 if limited by the range of the transfer integer
The transfer functions use unsigned integers (lsb and msb in fputi) where one might expect to see char variables. The longer length prevents overflow warnings in byte arithmetic and lost bits in left shifts. Unsigned integers also avoid the sign-fill uncertainty that occurs when using right shifts with signed numbers. A loophole in the C standard allows either the sign bit or zero to be put in the vacated upper bits [among other results — pjp]. If your compiler puts in zeros, a small negative number suddenly becomes a large positive one! The unsigned type also prevents unwanted sign extension that would occur with a signed char. Finally, although many K&R compilers do not support unsigned char, all C compilers have unsigned integers.
The first if statement traps -32,768 to prevent negation errors when obtaining the magnitude. If the number being sent is -32,768, the output bytes are set to the correct twos-complement value. For integer values other than -32,768, fputi splits the absolute value into two independent bytes. ANDing with 0xff limits the unsigned integers to eight bits. The magnitudes thus obtained are the same for any C integer format.
The magnitudes of negative numbers are restored to their signed value in the transfer format by operations that are independent of the compiler's representation. If *ip is negative, the algorithm negates the bytes in twos complement by first performing a bit-wise complement then adding one. Comparing *ip with -1 avoids problems with -0. The exclusive-OR negates only the lowest byte, leaving the upper bytes as they are (zero), whereas C's bit-wise negate operator would affect the entire variable.
The value at ip may have been out of range through all these operations if the host has integers longer than 16 bits. Postponing the range check until the end causes no processing problems because the value is masked down to bytes. The err variable eliminates an extra return. Unstacking variables for return consumes a significant amount of precious code space in a small microcontroller.
The range check determines if the value held in the host's integer, possibly four bytes long, has fit into the two transfer bytes. The only safe conditional test for MININT is a test for equality, because a twos-complement compiler may (erroneously) choose to negate MININT in a test for greater than. Although no problems were encountered in testing with type int, two compilers failed with long. Ecosoft's Eco-C Compiler Version 3.10 (1983) thought MINLNG was greater than all other negative long values. IBM's C/C++ Version 2.0 for OS/2 (1992) decided all positive long values were less than MINLNG. The other compilers got it right.
putc transfers the high-order byte (msb) first to create big-endian ordering in the file. The earlier byte masking serves another purpose when putc writes the bytes to the file. If lsb is not masked and happens to equal EOF, putc returns EOF whether or not there is an error.
The second function of Listing 1, fgeti, converts the transfer format of fputi to the host's format. Since twos complement is so common, most hosts will accept the full range of the transfer format. For those that meet only the minimum C range, however, the reaction to -32,768 is unpredictable. If the binary is accepted, it becomes -0 and propagates the wrong data. If the processor traps -0 as an error, the program may stop. In both cases, an out-of-range error from fgeti seems preferable.
After checking for transmission errors and masking, fgeti traps -32,768 if it is beyond MININT. The first if statement test creates a compile-time constant, TRUE or FALSE. The remaining portion always or never executes. Although the preprocessor's #if directive would serve better here, many K&R compilers do not support it. A code penalty is unlikely, however, because a compiler's optimizer often eliminates code sections that logically can't execute.
Sign restoration relies on positive integers being the same in all integer formats. If the transferred number is negative, fgeti sets the neg flag then negates the twos-complement value, making it positive. It then assembles the positive value byte-wise in an integer, ans. The host's arithmetic negation of ans assures that the sign is properly installed. Again, -32,768 must be handled separately because it has no positive counterpart. Identification is easy, since it is the only negative integer that remains negative after negation (0x8000+1 = 0x7fff+1 = 0x8000).
Knowing the host's format greatly simplifies both integer transfer functions. If the host is known to use 16-bit, twos-complement, MSB-first integers, use fwrite and fread for the transfer. If only the byte order is different (LSB-first), use memrev before fwrite and after fread.
Long Integer Transfers
The long integer transfer functions fputl and fgetl, in Listing 2, extend the integer transfer algorithm to four bytes. Like MININT, MINLNG equals either the host compiler's limit or the transfer limit, whichever is larger (least negative).At first glance, it might seem that the use of fputi and fgeti could simplify the coding. Just send the four-byte long integer as two two-byte integers. Unfortunately, the two least-significant bytes must be sent as an unsigned integer, and that doesn't work. Consider the long value 0x11118000. The lower bytes, 0x8000, are out-of-range for fgeti in some hosts. On the other hand, a host with 18-bit ones-complement integers would accept the value but produce the wrong bit pattern.
As in the case of integers, the function code can be simplified dramatically if the host is known to use twos-complement integers.
Floating-Point Transfers
Listing 3 shows fputf and fgetf, functions which convert the host's float formats to and from the four-byte IEEE-754 transfer format. The IEEE float has one sign bit, an 8-bit base-2 exponent biased by 127, and a 24-bit normalized mantissa that ranges from 1.0 to just less than 2 (about 1.999999881). The mantissa's always-present leading one is removed to pack the float into four bytes. It is restored prior to arithmetic operations. Table 2 gives some examples of floating-point values in IEEE-754 format.If faced with manually converting decimal numbers to this format (perhaps as punishment for the sins of one's youth), you could multiply or divide a number by powers of two until it fell in the 1.0 to 2.0 range. A tally of these scaling factors gives the power-of-two exponent. The mantissa is then factored into its binary fraction bits — with bits weighted 1.0, 0.5, 0.25, 0.125, etc. Binary fractions, however, reach the precision limit of a ten-digit calculator at 2-12 , leaving the range 2-13 to 2-23 beyond representation.
A better approach is to scale numbers to lie in the range 223 to 224-1. The binary factors are now easily represented as integers, 223 being 8,388,608. The IEEE-754 float value 0x3f800001 illustrates the practicality of the integer-factor approach and the difficulty of entering exact binary equivalents in decimal or of transferring them using printf. The binary factors are easily represented, but exact decimal representation of the total takes 24 digits.
value= (223+1)/223 * 2127-127 = (8388608+1)/8388608 * 1.0 = 1.00000011920928955078125Interpreting the mantissa as an integer also proves useful in the float transfer algorithm. The algorithm scales the float to the range 224-1 to 223 so that a float-to- long cast transfers all of the significant mantissa bits to the long. Another useful trick is exponent-only arithmetic, using only powers of two in scaling. Multiplication or division by powers of two means addition or subtraction in the exponent, which precludes errors caused by the finite mantissa precision. Even compilers limited to four-byte floats can perform the scaling and cast without error.Although the exponent of the popular IEEE-754 format represents powers of two, the exponent of the host format could represent powers of 4, 8, 10, or 16. As it turns out, these also convert without error when power-of-two scaling is used. Such formats do put some bits for the power-of-two factors in the mantissa, but the mantissa has more than enough precision to compute the modest 2127 range of the four-byte float without error.
The precision of the compiler sets a practical limit on the powers of two used in scaling. The compiler's strtod must convert the ASCII decimal representation of the power-of-two constants without error. A compiler with 23 bits of float precision can convert 20 to 224 without error, but fails on 225.
The fputf code begins with a special check for 0.0, which does not respond to scaling. The next steps take care of the sign. Two cascaded while loops scale the number's absolute value to one. The first deals only with small numbers, multiplying them to values greater than one in relatively large steps of 28. This leaves the number greater than 1.0 but no more than 256.0. The test for expo greater than zero stops the loop if the host's float is too small for the IEEE-574 format.
The second while loop handles numbers greater than one, including the result from the first while loop. This time all power-of-two factors present in the number are extracted. As in the first loop, initial scaling is in large 28 increments until the number gets within range (less than 28 in this case). The expo test stops the loop if the transfer range is exceeded. This prevents lockup if *np was the IEEE-574 representation of infinity, which, like zero, does not scale.
The two loops produce both the exponent and, upon multiplication by 223, the long integer mantissa. The encoding concludes with a byte-wise assembly of the IEEE-754 float in an array of characters. The range check uses the exponent rather than a maximum and minimum float value to avoid compiler inaccuracies in the ASCII-to-binary conversion. The putc loop sends the array (or zero) in MSB-first order.
The choice of 28 as the maximum scale factor minimizes conversion time. Scaling by 2.0 could be used, of course, but it would require 127 divisions to reduce 2127 to 20. The largest allowed constant, 223, hits a maximum when *np is 2114, requiring four divisions by 223 plus 22 sub-power scalings for a total of 26 divisions. By contrast, 28 scales 2127 down to 20 in 22 divisions. As it turns out, the optimum maximum scale factor is the square root of the exponent. The choice of 28 optimizes conversions in the mid-range of exponents (2*1019 to 2*10-19 ) where most physical measurements fall.
Moving on to fgetf, four bytes are checked for transmission errors as they are read into an array of unsigned integers, byt. Taking advantage of the loop set up for reading, they are also masked to eight bits and checked for zero. After unpacking the bytes to get expo and mant, a range check of expo intercepts erroneous or unintended values. Zero is also handled here since it won't scale.
The multiply and divide loops build the float exponent factor by error-free power-of-two arithmetic. The loops scale quickly by whole 28 factors, then finish the remainder (27 to 20) in a single arithmetic operation. The variable pwr contains 2expo-127 when done. The separate treatment based on the initial expo value prevents underflow or overflow in four-byte float hosts.
The error check detects most but not all host overflow problems. In hosts using four-byte float with an exponent bias of 128, for example, pwr usually denormalizes and/or reaches zero for numbers in the highest octave of the IEEE-754 range. The rest of the float range transfers accurately.
If pwr seems valid, the code negates it if the original sign bit was set. An intermediate variable, ftemp, prevents underflow by controlling the order of arithmetic operations.
Testing
Two programs are included on this month's code disk that aren't listed here. The first is a program to generate a file of test numbers. The second is a program to read the test number file and test the transfer routines. The transfer functions send data that will be the same in all computers that receive it. Be aware when testing, however, that the float data sent may not exactly match the originator's data due to rounding or truncation. Instead, the originator must process its data through fputf and fgetf, perhaps using a file, to have the same values as the other systems.Assume two systems, A and B, must share data originating in A. For simplicity, assume they can exchange data on a common floppy-disk format. To test the functions, system A writes a range of data to a binary file using fputi, fputl, and fputf. System B reads the file using fgeti, fgetl, and fgetf. From its internal data, system B creates a second file using the fput functions. It should be the duplicate of the one B just read. System A reads both files with fget functions, comparing them item by item.
Neither system should depend on a file-matching utility to compare the files, because A and B may use different fill characters in the unused space at the end of the file.