Implement routines for encoding, decoding, comparing, adding, subtracting, multiplying and dividing BCD (Binary Coded Decimal) numbers.
To encode a decimal number using the common BCD encoding, each decimal digit is stored in a 4-bit nibble. Thus, the BCD encoding for the number 127 would be: 0001 0010 0111. Whereas the pure binary number would be: 0111 1111.
Unlike binary-encoded numbers, BCD-encoded numbers can easily be displayed by mapping each of the nibbles to a different character. Converting a binary-encoded number to decimal for display is much harder, as this generally involves integer multiplication or divide operations. BCD also avoids problems where fractions that can be represented exactly in decimal cannot be represented in binary (e.g., one-tenth).
To illustrate this problem, run the following program and observe its output.
#include <stdio.h>
int main()
{
float g;
int i;
g = 0.0;
for (i = 0; i < 10000; i++)
g += 0.1;
printf("%g\n", g);
}
Since computers store data in 8-bit bytes, there are two common ways of storing 4-bit BCD digits in bytes:
each digit is stored in one nibble of a byte, with the other nibble being set to all zeros, all ones (as in the EBCDIC code), or to 0011 (as in the ASCII code)
two digits are stored in each byte.
For this project, we will only work with non-negative integers. We will use character arrays to store BCD numbers. The first element (or 0) of the array will be used to track how many digits are in the number. The other elements 1 through N will store one BCD digit each. Specifically, element i will store the digit in 10^(i-1)th position. For example, if 127 is store in character array m, then m[0], m[1], m[2], m[3] will have values 3, 7, 2, 1 respectively. Note that the digits are stored in order opposite to how characters in a string are stored. For instance, if m is used to store the string "127", then m[0], m[1], m[2], m[3] will have values '1', '2', '7', 0 respective. Informally, strings are stored left to right whereas BCD numbers are stored right to left. Since 0 is a valid BCD digit, we cannot use 0 (or '\0' character) to mark the last or left most digit in the BCD number. Hence our scheme for storing BCD numbers stores the length of the number in element 0. This is similar to how strings are stored in Pascal. Furthermore, note that when string "127" is stored, characters '1', '2', '7' are stored in array elements. However when BCD number 127 is stored, its the integers 1, 2, 7 that are stored.
Note that when 0 is encoded as BCD, it is always represented by a character array with 1 in first element and 0 in second element. It is an error to encoded 0 in any other way. For example, you should not encode 0 with 3 in the first element followed by 0 in the following 3 elements though this may produce equivalent results. In general, it is an error to have leading zeros in a BCD encoded number.
In this project, you will implement the following functions that perform basic arithmetic operations on BCD numbers.
| int bcd_encode(int i, int n, char *s) | Encode integer i into buffer s of size n. Returns 0 on success or -1 in case of an overflow (encoding i requires a buffer larger than n). |
| int bcd_decode(char *s) | Decode BCD number s to an integer. The decoded integer is the return value. |
| int bcd_gt(char *s, char *t) | Returns 1 if BCD number s is greater than BCD number t and 0 otherwise. |
| int bcd_eq(char *s, char *t) | Returns 1 if the two BCD numbers s and t are equal and 0 otherwise. |
| int bcd_add(char *s, char *t, int n, char *u) | Add two BCD numbers s and t and put the result in buffer u of size n allocated by the caller. Returns -1 if a larger buffer is required or 0 on success. |
| int bcd_sub(char *s, char *t, int n, char *u) | Subtract BCD number t from BCD number s and put the result in buffer u of size n allocated by the caller. If BCD number t is greater than BCD number s, the function returns -1 and no subtraction is carried out. The function also returns -1 if a larger buffer is required. On success it returns 0. |
| int bcd_mul(char *s, char *t, int n, char *u) | Multiply two BCD numbers s and t and put the result in buffer u of size n allocated by the caller. Returns -1 if a larger buffer is required or 0 on success. |
| int bcd_div(char *s, char *t, int n, char *u, int m, char *v) | Divide BCD number s by BCD number t and put the quotient (i.e. the result) in buffer u of size n allocated by the caller. The remainder is stored in buffer v of size m also allocated by the caller. Returns -1 if a larger buffer is required for storing either the quotient or the remainder. Also returns -1 in case of division by zero (BCD number t is 0). Returns 0 on success. |
Observe that all routines that return a BCD number take a caller allocated buffer of some specified size. These functions return -1 if the supplied buffer is inadequate to return the result (the result has more digits than that would fit in the buffer). If the buffer has size N, then only BCD numbers having at most N-1 digits can be placed into it since 1 element is taken for storing the size.
If you need a temporary buffer to store an intermediate result, use a buffer large enough to hold any BCD encoded 'int'.
To get started, please download the tarball provided HERE. To extract the archive type:
gzip -d prj1.tar.gz; tar xf prj1.tar
This will create directory prj1 and in there you will find files Makefile, main.c, prj1-bcd.h and prj1-bcd.c. Write all your code in file prj1-bcd.c. When grading we will replace all other files with our own. Hence if you modify other files the changes will be discarded. If you modify the prototypes, your project may not compile or produce correct results when we grade.
We do not provide a reference implementation for this project since its trivial to find out what the correct output should be. Observe however, this in no way implies that verifying your code works correctly is just as easy:)
Type cd .. in prj1 and change working directory to the parent directory of prj1.
In the parent directory of prj1, type turnin -v -c cs240=XXX -p prj1 prj1 to turnin your work. Replace XXX with your section number:
| 9:30 am - 11:20 am F | F930 |
| 11:30 am - 1:20 pm F | F1130 |
| 1:30 pm - 3:20 pm F | F130 |
| 3:30 pm - 5:20 pm F | F330 |
| 9:30 am - 11:20 am R | R930 |
| 11:30 am - 1:20 pm R | R1130 |
| 3:30 pm - 5:20 pm R | R330 |
| 11:30 am - 1:20 pm T | T1130 |
Now, you may use the command, turnin -c cs240=XXX -p prj1 -v to verify your submission.
This project is due on Sunday 6 February 11:59PM.