/*
 * udiv3-t.c : Dividing an unsigned number by 3 without using division and
 *             multiplication, but with the help of shift, add and subtract
 *             operations and table lookup. Number is manipulated in base 16
 *             representation.
 *
 * Copyright (C) 2006, Sandeep Kumar <shimple0@yahoo.com>
 *                     Homepage : http://sandeepkumar.fortunecity.com/
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details.
 */


#include <stdio.h>


/*
 * Arrays div3 and rem3 respectively contain quotient and remainder obtained
 * on dividing numbers from 0 to 47 by 3.
 *
 * udiv3_v1 uses only first (2+15) 17 entries (0 to 16) from these arrays, and
 * udiv3_v2 needs 48 entries (0 to "2*16 + 15") -- MAX [N%3] = 2 and maximum
 * value representable in 4 bits is 15.
 */

unsigned char div3[48] = {0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5 /**/
                          ,5,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10
                          ,11,11,11,12,12,12,13,13,13,14,14,14,15,15,15};

unsigned char rem3[48] = {0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1 /**/
                          ,2,0,1,2,0,1,2,0,1,2,0,1,2, 0, 1, 2
                          , 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2};


/*
 * Hint for the logic used in udiv3_v1 :
 * (a*X + b)/ 3 = (a/3)*X + ((a%3) * (X/3)) + (((a%3) * (X%3)) + b)/3
 */
unsigned short int udiv3_v1 (unsigned short int number)
{
    int ind, shiftcount = (((sizeof(number) << 1) - 1) << 2);
    __typeof__(number) mask = (0xF << shiftcount);
    register __typeof__(number) div = 0, rem = 0, temp;

    while (mask) {
        ind = (number & mask) >> shiftcount;

        /* Below "(rem * rem3[16])" can be replaced by just "rem". */
        temp = rem + rem3[ind];

        /* Below "(rem * div3[16])" can be replaced by just "(rem * 5)". */
        /* (rem * 5) = ((rem << 2) + rem) */
        div = (div << 4) + div3[ind] + div3[temp] + ((rem << 2) + rem);

        rem = rem3[temp];

        shiftcount -= 4;
        mask >>= 4;
    }

    return div;
}


/*
 * Hint for the logic used in udiv3_v2 :
 * (a*X + b)/ 3 = (a/3)*X + ((a%3)*X + b)/3
 */
unsigned short int udiv3_v2 (unsigned short int number)
{
    int ind, iter = (sizeof(number) << 1);
    const int shiftcount = (((sizeof(number) << 1) - 1) << 2);
    const __typeof__(number) mask = (0xF << shiftcount);
    register __typeof__(number) div = 0, rem = 0;

    while (iter--) {
        ind = (rem << 4) + ((number & mask) >> shiftcount);

        div = (div << 4) + div3[ind];
        rem = rem3[ind];

        number <<= 4;
    }

    return div;
}


int main (void)
{
    unsigned short int res, i = 0;
    int bug = 0;

    /* Regress test udiv3_v1. */
    do {
        res = udiv3_v1(i);

        if ((i/3) != res) {
            printf("BUG : (%d/3) = %d, udiv3(%d) = %d\n", i, (i/3), i, res);
            bug = 1;
        }


        i++;
    } while (0 != i);

    if (!bug)
        printf("Yippie! No Bug in udiv3_v1.\n");

    /* Regress test udiv3_v2. */

    /* i is already 0 : exit condition of previous while loop */
    bug = 0;
    do {
        res = udiv3_v2(i);

        if ((i/3) != res) {
            printf("BUG : (%d/3) = %d, udiv3(%d) = %d\n", i, (i/3), i, res);
            bug = 1;
        }

        i++;
    } while (0 != i);

    if (!bug)
        printf("Yippie! No Bug in udiv3_v2.\n");

    return 0;
}