分类： C/C++
2013-03-23 10:08:18
Part of
by
Copyright © 1999, Douglas. W. Jones, with major revisions made in 2002. This work may be transmitted or stored in electronic form on any computer attached to the Internet or World Wide Web so long as this notice is included in the copy. Individuals may make single copies for their own use. All other rights are reserved.
| Rated as a top 50 site by as of Feb 2002. |
Binary coded decimal arithmetic has fallen out of favor among modern hardware designers, and it is poorly supported in most modern programming languages, yet it is still occasionally appropriate. For example, when a numeric field of a record in a text file must be incremented, the methods presented here will be significantly faster than converting the textual value to a binary integer, incrementing, and then converting back to text.
For programmers with a devious sense of humor, these methods can be a very effective way to obfuscate code in languages such as C. These techniques are also historically significant. The DEC (now Compaq) Alpha architecture and the more recent Intel MMX extensions to the 80x86 architecture both supporting manipulation of vectors of small objects such as pixels packed into 64-bit words; the motive for this can be found in the much older ideas described here.
In the following sections, all arithmetic is assumed to be done in 32 bit registers (the algorithms are easily adapted to other word lengths), and neither carry out nor overflow are deemed significant. The code written for clarity, using C notation for operators and constants, with named temporary variables whenever a subexpression in the computation is cited in the text. Practical implementations will very likely use far fewer temporary variables.
All of the number representations discussed here are unsigned, although the subtraction operation rests on the use of ten's complement arithmetic, and this, in turn, suggests the use of the ten's complement operation for negation. In that case, number with a most significant digit greater than 5 can be interpreted as negative numbers.
For unsigned decimal numbers (or for 10's complement numbers with the same sign), the conventional unsigned binary comparison operators all remain applicable with these decimal represenations. Thus, if A and B are unsigned decimal numbers, and if > is the conventional unsigned greater-than operator for binary numbers, A>B will yield the correct results for comparing these numbers.
The programmer interested in efficient BCD to Binary conversion should also check out the code in appendix I.5 of the paper "Superoptimizer -- A Look at the Smallest Program" by Henry Massalin, Proc. Second Int. Conf. on Arch. Support for Prog. Lang. and Op. Sys. (ASPLOS II) published as Computer Architecture News 15 , 5 (Oct. 1987).
Binary coded decimal numbers may be represented in a number of ways. The most obvious is packed BCD, where each decimal digit is represented by a 4 bit field, and the digits are packed consecutively into a computer word. This scheme allows 4 digits to be packed into a 16 bit word, or 8 digits into a 32 bit word, as shown below.
B31 B15 B0
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
| D7 | D6 | D5 | D4 | D3 | D2 | D1 | D0 |
In addition to its efficiency, this format is useful because it is compatable with the use of hexidecimal I/O routines. Traditionally, packed BCD was viewed as requiring the use of special hardware to do BCD arithmetic, but in fact, it is possible to add two packed BCD numbers using a short sequence of conventional binary and logical operators.
Many early computers used 6-bit BCD codes, where each BCD digit was padded to 6 bits. This was compatable with the 36, 48 and 60 bit words used by many computers in the 1950's and 1960's, and on both the 36-bit IBM 704-709 series of machines (up through the 7044 and 7094) and 60-bit CDC 6600 series, this format was used to do BCD arithmetic without any special hardware support. On a modern 16 or 32 bit machine, this allows 3 or a bit more than 5 decimal digits per word, respectively.
B31 B15 B0
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
| D5|0 0| D4 |0 0| D3 |0 0| D2 |0 0| D1 |0 0| D0 |
In the 32 bit format, productive use can be made of the fractional digit D5 for carry detection and propagation in extended precision arithmetic operations.
It should be noted that in most historically important 6-bit BCD collating sequences, all numerals other than zero were represented as shown above, while zero was sometimes represented by the binary code 1010, allowing the 6-bit code 000000 to be used for space. Ones in the two most significant bits of each 6-bit byte were used in the codes for letters and punctuation marks. See material on for more detail on this subject.
The methods discussed here can be extended to other padding systems in obvious ways. For example, 6 5-bit fields can be packed into a 32-bit word, with one bit of padding between BCD digits. Alternately, 3 bits of padding can be added between digits, so that a 32-bit word holds 4 complete 7-bit fields, plus 4 bits that can be used for a 5th BCD digit.
Padding each BCD digit to fill an 8 bit byte is quite practical, but this inefficient representation is not particularly interesting except in the special case where each digit is directly represented by its ASCII code , as follows:
B31 B15 B0
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|0 0 1 1| D3 |0 0 1 1| D2 |0 0 1 1| D1 |0 0 1 1| D0 |
Of course, the same approach can be used for EBCDIC, using 0xF for a pad digit instead of 0x3 . It is quite practical to do arithmetic operations directly on all of these representations!
The least significant 7 digits of a packed BCD number may be tested for validity as follows:
valid(a)
t1 = a + 0x06666666
t2 = a ^ 0x06666666
t3 = t1 ^ t2
t4 = t3 & 0x11111110
if t4 nonzero, a is invalid
This code deliberately ignores D7, the most significant digit, because the arithmetic operators presented here allow this digit to hold values up to 15. To understand this code, note that binary addition of 6 to each digit, to produce t1 , will cause any digit with a value greater than 9 to generate a carry into the next higher digit.
t2 is similar to t1 , in the sense that exclusive-oring is similar to adding. The two will be equal in bits where there was no carry in to that position, but they will differ in bits where there was a carry in. Therefore, t3 holds a one wherever there was a carry into a bit of t1 , and t4 holds a 1 wherever there was a carry into a BCD digit of t1 . Since the addition used to produce t1 should not produce such carries for a valid BCD number, t4 should be zero!
valid(a)
t1 = a + 0x06666666
t2 = t1 ^ a
t3 = t2 & 0x11111110
if t3 nonzero, a is invalid
The above improvement was suggested by John Mertus at Brown University; Here, note that adding 6 to a 4-bit nibble of a produces a carry out of that nibble if the nibble is invalid, but also, adding 6 does not change the least significant bit. By exclusive oring the result in t1 with a to make t2 , the least significant bit of each nibble is compared with the original. Finally, we ignore all the other bits and demand that all the least significant bits be zero, indicating no carry from the previous bit positions.
Antoine Schweitzer-Chaput suggested an alternative validity check to me. Note that all BCD digits of the form 0xxx are valid, as are digits of the form x00x. Therefore, if d is a BCD digit, we can test it for validity with:
valid(d)
if (d & 0x8) is zero or (d & 0x6) is zero
Extending this to packed BCD is a fun challenge.
The code to add two BCD numbers must solve the problem of propagating carries from one BCD digit to the next, and the logic for doing so rests on many of the mechanisms introduced above.
add(a,b)
t1 = a + 0x06666666
t2 = t1 + b
t3 = t1 ^ b
t4 = t2 ^ t3
t5 = ~t4 & 0x11111110
t6 = (t5 >> 2) | (t5 >> 3)
return t2 - t6
Here, the addition used to form t1 should not produce any carries, since we assume that t1 is valid. The addition used to form t2 will produce a carry exactly when the decimal addition of two digits in the operands would produce a carry, and these are the carries we are concerned with.
In t2 , the digits in each position that produced a carry will have the correct value, but the digits in positions that did not produce a carry will contain an excess 6. The problem, then, is to remove the extra 6 from each digit that did not generate a carry.
Note that t2 and t3 differ wherever there was a carry, so t4 records all carries into positions in the sum. Therefore, t5 holds the inverse of each of the 7 carries between successive decimal digits of the sum. This bit pattern is used to generate t6 , where each digit is either 6 where the corresponding digits of the sum did not generate a carry or 0 where they did. Subtracting this from t2 produces the correct BCD sum.
Note that the most significant digit of the sum will exceed 9 if there should have been a carry out of that position. Furthermore, there is no easy way to detect this carry! Out of range values in the high digit may be of some limited use, but in general, the top BCD digit should only be used to accumulate carrys out of 7-digit BCD operands. If its use is limited in this way, the numbers will always be positive and will never produce a 2's complement overflow.
To subtract two numbers, 10's complement addition should be used. To compute the 10's complement of a number, subtract it digit-by-digit from 99999999 (decimal) and then add 1, as follows:
tencomp(a)
t1 = 0xF9999999 - a
return add( t1, 0x00000001 )
Here, t1 is (mostly) the 9's complement of the argument, except that the topmost digit is the 15's complement because of the redundancy allowed in that digit position. There is room for optimization in this code! As a first step, the code for addition has been substituted into place (with appropriate variable renaming).
tencomp(a)
t1 = 0xF9999999 - a
t2 = t1 + 0x06666666
t3 = t2 + 0x00000001
t4 = t2 ^ 0x00000001
t5 = t3 ^ t4
t6 = ~t5 & 0x11111110
t7 = (t6 >> 2) | (t6 >> 3)
return t3 - t7
This reduces to the following obscure bit of code, with variables renamed again:
tencomp(a)
t1 = 0xFFFFFFFF - a
t2 = - a
t3 = t1 ^ 0x00000001
t4 = t2 ^ t3
t5 = ~t4 & 0x11111110
t6 = (t5 >> 2) | (t5 >> 3)
return t2 - t6
All 5 full digits of a 6-bit BCD number may be tested for validity as follows:
valid(a)
t1 = a + 006666666666
t2 = t1 & 006060606060
if t2 = 006060606060, a is valid
To understand this code, note that binary addition of 066 to each digit, to produce t1 , will cause any digit with a value greater than 9 to generate a carry into the next higher digit. The lower 6 forces a carry out of any digit greater than 9, while the higher 6 sets the pad bits and allows the carry to propagate up to the next higher digit position.
t2 holds just the pad bits in the result from t1 . Where no carry was propagated in the computation of t1 , these will be set, while where a carry was propagated through the padding, they will be reset. A valid 6-bit BCD number should not have generated any carry, so all of the pad bits should be set!
The code to add two 5-digit 6-bit BCD numbers must solve the problem of propagating carries from one BCD digit to the next, and the logic for doing so rests on the mechanisms just introduced:
add(a,b)
t1 = a + b + 006666666666
t2 = t1 & 006060606060
return t1 - (t2 >> 3)
Here, the addition used to form t1 adds an extra 6 to each BCD digit, forcing a carry out of that digit if the sum exceeds 9, and the same constant also includes ones in each pad bit in order to force this cary to propagate up to the next higher digit.
In t1 , the digits in each position that produced a carry will have the correct value, but the digits in positions that did not produce a carry will contain an excess 6. The problem, is to remove this 6 from each digit that did not generate a carry.
t2 contains just the pad bits from the sum. For those digits that did not produce a carry, the pad bits will still be set to one. For those digits that produced a carry, the pad bits will be set to zero by the propagagion of the carry.
Shifting t2 3 places right produces a 6 in each digit position that did not generate a carry and zero elsewhere. Subtracting this from t1 produces the required correction!
A carry out from the 5-digit BCD sum will appear in partial digit, D5, that occupies the topmost 2 bits of the 32 bit number.
To subtract two numbers, 10's complement addition should be used. To compute the 10's complement of 5-digit 6-bit BCD number, subtract it digit-by-digit from 99999 (decimal) and then add 1, as follows:
tencomp(a)
t1 = 001111111111 - a
return add( t1, 000000000001 )
Here, t1 is the 9's complement of the argument (note that 11 octal is 9 decimal). There is considerable room for optimization in this! Substituting the definition of add and renaming the variables to avoid collision, we get:
tencomp(a)
t1 = 001111111111 - a
t2 = t1 + 000000000001 + 006666666666
t3 = t2 & 006060606060
return t2 - (t3 >> 3)
Rearranging terms and renaming temporaries gives:
tencomp(a)
t1 = (001111111111 - a)
+ 000000000001
+ 006666666666
t2 = t1 & 006060606060
return t1 - (t2 >> 3)
Which simplifies to:
tencomp(a)
t1 = 010000000000 - a
t2 = t1 & 006060606060
return t1 - (t2 >> 3)
To verify that a 4-digit ASCII string contains only valid BCD codes, techniques similar to those used for packed BCD and 6-bit BCD can be used:
valid(a)
t1 = a + 0xC6C6C6C6
t2 = t1 & 0xF0F0F0F0
if t2 = 0xF0F0F0F0, a is valid
To understand this code, note that binary addition of 0xC6 to each digit, to produce t1 , will cause any digit with a value greater than 9 to generate a carry into the next higher digit. The lower 6 forces a carry out of any digit greater than 9, while the higher 0xC sets those pad bits which were not already set in the ASCII representation of the digit, thus allowing the carry to propagate up to the next higher digit position.
t2 holds just the pad bits from t1 . Where no carry was propagated in the computation of t1 , these will be set, while where a carry was propagated, they will be reset. A valid 6-bit BCD number should not have generated any carry, so all pad bits should be set!
Validity checking is more complex if blank and zero are to be interchangable, and more complex still if only leading blanks are allowed. On the other hand, oring 0x10101010 with a potential number converts all blanks to zeros, while also converting certain punctuation marks to other numerals. In certain applications, this may be a reasonable way to deal with blanks.
The code to add two 4-digit ASCII numbers must solve the problem of propagating carries from one BCD digit to the next, and the logic for doing so rests on the mechanisms just introduced:
add(a,b)
t1 = a + b + 0x96969696
t2 = t1 & 0x30303030
t3 = t1 - (t2 >> 3)
return (t3 & 0x0F0F0F0F) | 0x30303030
Here, the addition used to form t1 adds an extra 6 to each BCD digit, forcing a carry out of that digit if the sum exceeds 9. In addition, it sets those pad bits which would not already be set by the padding included in ASCII for each character. This forces carry propagation up to the next higher digit.
In t1 , the digits in each position that produced a carry will have the correct value, but the digits in positions that did not produce a carry will contain an excess 6.
t2 contains the two least significant bits of the padding from the sum; these bits will be 1 where no carry was propagated, so they can be shifted to subtract the excess 6 from the adjacent digit of the sum. This corrected sum, in t3 still contains the incorrect values in the pad fields. No matter what we do, it seems to take two extra binary operations to restore the pad fields to their proper values.
The carry out from the 4-digit ASCII sum can be extracted from the pad bits of any of the temporary variables used above, so no digits are wasted in extended precision ASCII arithmetic.
By all means, if your purpose is to write obfuscated code, and if your programming language allows it, substitute ASCII literals for the hex constants wherever possible, as follows:
add(a,b)
t1 = a + b + 0x96969696
t2 = t1 & '0000'
t3 = t1 - (t2 >> 3)
return (t3 & 0x0F0F0F0F) | '0000'
To subtract two numbers, 10's complement addition should be used. To compute the 10's complement of a number, subtract it digit-by-digit from 9999 (decimal) and then add 1, as follows:
tencomp(a)
t1 = 0x69696969 - a
return add( t1, 0x30303031 )
Here, t1 is the 9's complement of the argument; the tricky aspect in this case is that the pad bits of the argument are nonzero, so the constant 9999 must be padded strangely to create the correct results. In any case, there is considerable room for optimization in this code! Substituting the code for addition and renaming temporaries gives:
tencomp(a)
t1 = 0x69696969 - a
t2 = t1 + 0x30303031 + 0x96969696
t3 = t2 & 0x30303030
t4 = t2 - (t3 >> 3)
return (t4 & 0x0F0F0F0F) | 0x30303030
Combining terms, renaming, and simplifing the result gives the following strange bit of code:
tencomp(a)
t1 = 0x20202020 - a
t2 = t1 & 0x30303030
t3 = t1 - (t2 >> 3)
return (t3 & 0x0F0F0F0F) | 0x30303030
Of course, if your purpose is to write obfuscated code, by all means substitute ASCII literals for the hex constants wherever possible, creating:
tencomp(a)
t1 = ' ' - a
t2 = t1 & '0000'
t3 = t1 - (t2 >> 3)
return (t3 & 0x0F0F0F0F) | '0000'
Much of the complexity of the above code is imposed by computations that determine the carry out of each digit of the BCD sum. Hardware that allows the carry propagation from bit to bit of the adder to be interrupted at selected points can greatly speed these computations. Both the DEC (later Compaq) Alpha and the Intel MMX extensions to the 80x86 family provide for this, allowing 64 bit words to be divided into many subfields, with carry propagation from field to field interrupted, and with the carries captured in a form allowing their manipulation. These facilities are not exposed to the high level language programmer, but they are used intensively in carefully handcrafted assembly-language routines for common vector operations such as those involved in pixel manipulation of graphics images.