Make an binary addition behave like a (packed-) decimal addition

Question

I'm currently working on a restrictive environment where the only types allowed are :

byte, byte[], short, short[].

I am almost certain that I can't import external libraries, since I'm working on a JavaCard, and have already tried such things, which didn't turn out good.

So, here I have to manage a byte array with a size of 6 bytes, which represents the balance of the card (in euros), and the last byte are cents, but this is not important now.

Given that I don't have access to integers, I don't know how I can add two byte in the way I want.

Let's have an example :

User puts in (Add) 0x00 0x00 0x00 0x00 0x00 0x57, which, to the user, means add 57 cents. Let's now say that the balance is 0x00 ... 0x26.

I want to be able to create a method that could modify the balance array (with carries), in a way that after adding, the cents are 83, and represented 0x83. I have to handle subtractions as well, but I guess I can figure that out for myself afterwards.

My first guess was mask out each digit from each byte, and work separately at first, but that got me nowhere.

I'm obviously not asking for a full solution, because I believe my problem is almost impossible, but if you have any thoughts on how to approach this, I'd be very grateful.

So how can I add two arrays containing binary coded decimals to each other on Java Card?

---

EDIT 1: A common array would look like this :

{ 0x00 , 0x00 , 0x01, 0x52, 0x45, 0x52}

and would represent 15 254€ and 52 cents in a big-endian BCD encoded integer.

---

EDIT 2 : Well, as I suspected, my card doesn't support the package framework.math, so I can't use BCDUtil or BigNumbers, which would've been useful.

Answer 1

The below implementation goes through the BCD byte-by-byte and digit by digit. This allows it to use 8 bit registers that are efficient on most smart card processors. It explicitly allows for the carry to be handled correctly and returns the carry in case of overflow.

/**
 * Adds two values to each other and stores it in the location of the first value.
 * The values are represented by big endian, packed BCD encoding with a static size.
 * No validation is performed if the arrays do indeed contain packed BCD;
 * the result of the calculation is indeterminate if the arrays contain anything other than packed BCD.
 * This calculation should be constant time;
 * it should only leak information about the values if one of the basic byte calculations leaks timing information.
 *
 * @param x the first buffer containing the packed BCD
 * @param xOff the offset in the first buffer of the packed BCD
 * @param y the second buffer containing the packed BCD
 * @param yOff the offset in the second buffer of the packed BCD
 * @param packedBytes the number of bytes that contain two BCD digits in both buffers
 * @return zero or one depending if the full calculation generates a carry, i.e. overflows
 * @throws ArrayIndexOutOfBoundsException if a packed BCD value is out of bounds
 */
public static byte addPackedBCD(byte[] x, short xOff, byte[] y, short yOff, short packedBytes) {
    // declare temporary variables, we'll handle bytes only
    byte xd, yd, zd, z;
    // set the initial carry to zero, c will only be 0 or 1
    byte c = 0;
    // go through the bytes backwards (least significant bytes first)
    // as we need to take the carry into account
    for (short i = (short) (packedBytes - 1); i >= 0; i--) {
        // retrieve the two least significant digits the current byte in the arrays
        xd = (byte) (x[xOff + i] & 0b00001111);
        yd = (byte) (y[yOff + i] & 0b00001111);
        // zd is the addition of the lower two BCD digits plus the carry
        zd = (byte) (xd + yd + c);
        // c is set to 1 if the final number is larger than 10, otherwise c is set to zero
        // i.e. the value is at least 16 or the value is at least 8 + 4 or 8 + 2
        c = (byte) (((zd & 0b10000) >> 4)
                | (((zd & 0b01000) >> 3)
                        & (((zd & 0b00100) >> 2) | ((zd & 0b00010) >> 1))));
        // subtract 10 if there is a carry and then assign the value to z
        z = (byte) (zd - c * 10);

        // retrieve the two most significant digits the current byte in the arrays
        xd = (byte) ((x[xOff + i] >>> 4) & 0b00001111);
        yd = (byte) ((y[yOff + i] >>> 4) & 0b00001111);
        // zd is the addition of the higher two BCD digits plus the carry
        zd = (byte) (xd + yd + c);
        // c is set to 1 if the final number is larger than 10, otherwise c is set to zero
        // i.e. the value is at least 16 or the value is at least 8 + 4 or 8 + 2
        c = (byte) (((zd & 0b10000) >> 4)
                | (((zd & 0b01000) >> 3)
                        & (((zd & 0b00100) >> 2) | ((zd & 0b00010) >> 1))));
        // subtract 10 if there is a carry and then assign the value to the 4 msb digits of z
        z |= (zd - c * 10) << 4;

        // assign z to the first byte array
        x[xOff + i] = z;
    }

    // finally, return the last carry
    return c;
}

---

Note that I have only tested this for two arrays containing a single byte / two BCD digits. However, the carry works and as all 65536 combinations have been tested the approach must be valid.

---

To top it off, you may want to test the correctness of the packed BCD encoding before performing any operation. The same approach could be integrated into the for loop of the addition for higher efficiency. Tested against all single byte values as in the previous block of code.

/**
 * Checks if the buffer contains a valid packed BCD representation.
 * The values are represented by packed BCD encoding with a static size.
 * This calculation should be constant time;
 * it should only leak information about the values if one of the basic byte calculations leaks timing information.
 *
 * @param x the buffer containing the packed BCD
 * @param xOff the offset in the buffer of the packed BCD
 * @param packedBytes the number of bytes that packed BCD in the buffer
 * @return true if and only if the value is valid, packed BCD
 * @throws ArrayIndexOutOfBoundsException if the packed BCD value is out of bounds
 */
public static boolean validPackedBCD(byte[] x, short xOff, short packedBytes) {
    // declare temporary variable, we'll handle bytes only
    byte xdd;
    // c is the correctness of the digits; it will be off-zero if invalid encoding is encountered
    byte c = 0;

    short end = (short) (xOff + packedBytes);
    // go through the bytes, reusing xOff for efficiency
    for (; xOff < end; xOff++) {
        xdd = x[xOff];
        // c will be set to non-zero if the high bit of each encoded decimal is set ...
        // and either one of the two decimals is set as that would indicate a value of 10 or higher
        // i.e. only values 8 + 4 or 8 + 2 are 10 or higher if you look at the bits in the digits
        c |= ((xdd & 0b1000_1000) >> 2) & (((xdd & 0b0100_0100) >> 1) | (xdd & 0b0010_0010));
    }

    // finally, return the result - c is zero in case all bytes encode two packed BCD values
    return c == 0;
}

Note that this one is also implemented in BCDUtil in Java Card. I do however dislike that class design and I don't think it is that well documented, so I decided for a different tack on it. It's also in javacardx which means that it could theoretically throw an exception if not implemented.

---

The answer of EJP isn't applicable, other than to indicate that the used encoding is that of packed BCD. The addition that Jones proposes is fast, but it doesn't show how to handle the carry between the 32 bit words:

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!

This is of course required for Java Card as it only has 16 bit signed shorts a base type integer. For that reason the method that Jones proposes is not directly applicable; any answer that utilizes the approach of Jones should indicate how to handle the carry between the bytes or shorts used in Java Card.

Answer 2

This is not really hex, it is packed decimal, one of the forms of BCD.

You can do packed-decimal addition and subtraction a byte at a time, with internal carry. There is a trick of adding 6 to force a carry into the MS digit, if necessary, and then masking and shifting it out again if it carried, to correct the LS digit. It's too broad to explain here.

See Jones on BCD arithmetic which shows how to efficiently use bit operands on 32 bit words to implement packed decimal arithmetic.