Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/tumble.cxx

Go to the documentation of this file.

/**********************************************************************
 * Copyright 2002 Jeff Rush <jrush@taupro.com>
 * Original Copyright 1979-2002 Udanax.com
 *
 * This file is part of the Udanax xanalogical storage system.
 *
 * Udanax 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.
 *
 * Udanax 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.
 *
 * You should have received a copy of the GNU General Public License
 * along with Udanax; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 **********************************************************************/

/* Modification History:
 * $Log: tumble.cxx,v $
 * Revision 1.12  2004/09/11 13:59:21  jrush
 * Changed all fprintf's to stderr to use the Nana library L() macro.  Also
 * removed a 2-3 minor compiler warnings.
 *
 * Revision 1.11  2004/09/04 16:02:18  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.10  2002/07/14 08:35:24  jrush
 * Replace gerror(), qerror() with assert()
 *
 * Revision 1.9  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.8  2002/05/28 02:52:23  jrush
 * Made static any functions and global variables private to this source file
 * and commented out any unused functions.
 *
 * Revision 1.7  2002/04/12 22:53:20  jrush
 * Changed from using my setmem() to the clib's memset() and removed no
 * longer-needed usefull.cxx
 *
 * Revision 1.6  2002/04/12 11:56:43  jrush
 * Reorganized include file layout, renamed xanadu.h to udanax.h and
 * typecontext/typecrumcontext to C++ class Context/CrumContext.
 *
 * Revision 1.5  2002/04/09 21:45:46  jrush
 * Renamed class 'tumbler' to 'Tumbler', for consistency with Python sources,
 * and changed typeisa from typedef to a subclass, in preparation for cleaning
 * up the type/class tree.
 *
 * Revision 1.4  2002/04/06 19:51:30  jrush
 * Renamed TRUE/FALSE constant use to the C++ standard of true/false.
 *
 * Revision 1.3  2002/04/06 15:01:17  jrush
 * Changed INT to just 'int'.
 *
 * Revision 1.2  2002/02/14 09:27:43  jrush
 * Cleaned up source:
 *
 * 1. ran thru the indent tool to achieve a standard look,
 * 2. added structured comments at top for use with DOxygen reporting
 *    as well as CVS keywords,
 * 3. fixed compiler warnings re ambiguous assign/compares,
 *    needed casts and unused/uninitialized variables,
 * 4. fixed funcs that didn't specify a return type,
 * 5. centralized prototypes in protos.h, removing incomplete ones,
 * 6. cleaned up use of bool/BOOLEAN type to suit C++ type,
 * 7. fixed initializer nesting in tumbler constants,
 * 8. renamed vars that conflict with C++ keywords (new, this),
 * 9. fixed global/extern confusion re some global vars.
 *
 */

#include "udanax.h"

Tumbler ZEROTUMBLERvar;

static int abscmp(Tumbler *aptr, Tumbler *bptr);

/* ---------------- Routines to test tumblers -------------- */

    bool
tumblereq(
    Tumbler *a,
    Tumbler *b)
{
    char *aptr = (char *)a;    /* char * for cheating in compare loop */
    char *bptr = (char *)b;
    int i;

/* return (tumblercmp (aptr, bptr) == EQUAL);// old safe & slow// */
/* could speed up by doing comparison directly or stealing from abscmp */
    i = (int)aptr + sizeof(Tumbler);
    for (; ((int)aptr) < i;) {
        if (*aptr++ != *bptr++)
            return false;
    }
    return true;
}

    bool
tumbleraccounteq(
    Tumbler *aptr,
    Tumbler *bptr)
{
    int i, j;

    if (aptr->exp != bptr->exp || aptr->sign != bptr->sign)
        return false;

    for (j = 0, i = 0; i < NPLACES; i++) {
        if (aptr->mantissa[i] != bptr->mantissa[i])
            return false;

        if (aptr->mantissa[i] == 0 && ++j == 2)
            return true;
    }
    return true;
}

    int
tumblercmp(
    Tumbler *aptr,
    Tumbler *bptr)
{
    if (iszerotumbler(aptr)) {
        if (iszerotumbler(bptr))
            return EQUAL;
        else
            return (bptr->sign ? GREATER : LESS);
    }

    if (iszerotumbler(bptr))
        return (aptr->sign ? LESS : GREATER);

    if (aptr->sign == bptr->sign)
        return (aptr->sign ? abscmp(bptr, aptr) : abscmp(aptr, bptr));

    return (aptr->sign ? LESS : GREATER);
}

#ifndef ExPeriMental

    static int
abscmp(
    Tumbler *aptr,
    Tumbler *bptr)
{
    int *a, *b;
    int i, cmp;

    if (aptr->exp != bptr->exp) {
        if (aptr->exp < bptr->exp) {
            return LESS;
        } else {
            return GREATER;
        }

    } else {
        a = (int *) aptr->mantissa;
        b = (int *) bptr->mantissa;
        for (i = NPLACES; i--;) {
            if (!(cmp = *a++ - *b++)) {
            } else if (cmp < 0) {
                return LESS;         /* a < b */
            } else {                   /* if (cmp > 0) */
                return GREATER;
            }
        }
    }
    return EQUAL;
}
#else

    static int
abscmp(
    Tumbler *aptr,
    Tumbler *bptr)
{
    int *a, *b;
    int i, cmp;

    if (aptr->exp != bptr->exp) {
        if (aptr->exp < bptr->exp) {
            return LESS;
        } else {
            return GREATER;
        }
    } else {
        a = (int *) aptr->mantissa;
        b = (int *) bptr->mantissa;
        for (i = NPLACES; i--;) {
            cmp = *a - *b;
            if (cmp == 0) {            /* this is an efficiency hack */
                a++;
                b++;
                continue;
            } else if (cmp < 0) {
                return LESS;         /* a < b */
            } else {                   /* if (cmp > 0) */
                return GREATER;
            }
        }
    }
    return EQUAL;
}
#endif

    int
intervalcmp(
    Tumbler *left,
    Tumbler *right,
    Tumbler *address)
{
    int cmp;

    cmp = tumblercmp(address, left);
    if (cmp == LESS)
        return TOMYLEFT;

    else if (cmp == EQUAL)
        return ONMYLEFTBORDER;

    cmp = tumblercmp(address, right);
    if (cmp == LESS)
        return THRUME;
    else if (cmp == EQUAL)
        return ONMYRIGHTBORDER;
    else
        return TOMYRIGHT;
}

/* bool iszerotumbler(tumblerptr) tumbler *tumblerptr; { return(!(tumblerptr -> mantissa[0])); } */

    bool
tumblercheckptr(
    Tumbler *ptr,
    int /* typecrum */  *crumptr)
{
    bool wrong;
    int i;

    wrong = false;
    if (ptr->exp > 0) {
#ifndef DISTRIBUTION
        L("bad exp ");
#endif
        wrong = true;
    }

    if (ptr->sign && ptr->mantissa[0] == 0) {
#ifndef DISTRIBUTION
        L(" negative zero ");
#endif
        wrong = true;
    }

    if (ptr->exp && ptr->mantissa[0] == 0) {
#ifndef DISTRIBUTION
        L("fucked up non-normalized");
#endif
        wrong = true;
    }

    if (ptr->mantissa[0] == 0) {
        for (i = 1; i < NPLACES; ++i) {
            if (ptr->mantissa[i] != 0) {
#ifndef DISTRIBUTION
                L("nonzerozerotumbler");
#endif
                wrong = true;
            }
        }
    }

    for (i = 0; i < NPLACES; ++i) {
        if ((int) (ptr->mantissa[i]) < 0) {
#ifndef DISTRIBUTION
            L("negative digit");
#endif
            wrong = true;
        }
    }

    if (wrong) {
#ifndef DISTRIBUTION
        dumptumbler(ptr);
        if (crumptr) {
            dump((typecorecrum *) crumptr);
        }
        L("\n\n invalid tumbler \n\n");
        if (crumptr) {
            dumpwholetree((typecorecrum *) crumptr);
        }
        assert(0); // invalid tumbler
#else
        assert(0);
#endif
        return false;
    }

    return true;
}

    bool
tumblercheck(
    Tumbler *ptr)
{
    return tumblercheckptr(ptr, (int *) NULL);
}

/* says whether there is no more than a single non-zero ** digit in mantissa */
    bool
is1story(
    Tumbler *tumblerptr)
{
    int i;

    //assert( tumblercheck(tumblerptr) );
    
    for (i = 1; i < NPLACES; i++)
        if (tumblerptr->mantissa[i] != 0)
            return false;
    return true;
}

    int
nstories(
    Tumbler *tumblerptr)
{
    int i;

    //assert( tumblercheck(tumblerptr) );
    
    for (i = NPLACES; i > 0 && tumblerptr->mantissa[--i] == 0; )
        ;

    return i + 1;
}

    int
tumblerlength(
    Tumbler *tumblerptr)
{
    return nstories(tumblerptr) - tumblerptr->exp;
}

/* int nzeroesintumbler (tumblerptr) tumbler *tumblerptr; { int n, i, count; n = nstories (tumblerptr); for (count = i 
 * = 0; i < n; ++i) if (tumblerptr->mantissa[i] == 0) ++count; count -= tumblerptr->exp; return (count); } */

    int
lastdigitintumbler(
    Tumbler *tumblerptr)
{
    int n, digit;

    n = nstories(tumblerptr);
    digit = tumblerptr->mantissa[n - 1];
    return digit;
}

/* --------- Routines below set and change tumblers -------- */

    void
tumblerjustify(
    Tumbler *tumblerptr)
{
    int i, j;
    int shift;
    tdigit *mantissaptr;

    mantissaptr = tumblerptr->mantissa;
    if (mantissaptr[0] != 0)
        return;

    for (shift = 0; mantissaptr[shift] == 0; ++shift) {
        if (shift == NPLACES - 1) {
            tumblerptr->exp = 0;
            tumblerptr->sign = 0;
            return;
        }
    }

    for (i = 0, j = shift; j < NPLACES;)
        mantissaptr[i++] = mantissaptr[j++];

    while (i < NPLACES)
        mantissaptr[i++] = 0;

    tumblerptr->exp -= shift;

    //assert( tumblercheck(tumblerptr) );
}

    static void
partialtumblerjustify(
    Tumbler *tumblerptr)
{
    int i, j;
    int shift;
    tdigit *mantissaptr;

    mantissaptr = tumblerptr->mantissa;
/* test commented out because is done before this routine is called for efficiency */
/* if (mantissaptr[0] != 0) { return; } */
    for (shift = 0; mantissaptr[shift] == 0; ++shift) {
        if (shift == NPLACES - 1) {
            tumblerptr->exp = 0;
            tumblerptr->sign = 0;
            return;
        }
    }

    for (i = 0, j = shift; j < NPLACES;)
        mantissaptr[i++] = mantissaptr[j++];

    while (i < NPLACES)
        mantissaptr[i++] = 0;

    tumblerptr->exp -= shift;

    //assert( tumblercheck(tumblerptr) );
}

    void
tumblercopy(
    Tumbler *fromptr,
    Tumbler *toptr)
{
/* movmem (fromptr, toptr, sizeof(tumbler)); */
    movetumbler(fromptr, toptr);
}

/* tumblermin (aptr, bptr, cptr) register tumbler *aptr, *bptr, *cptr; { if (tumblercmp (aptr, bptr) == LESS)
 * movetumbler (aptr, cptr); else movetumbler (bptr, cptr); } */

    void
tumblermax(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    if (tumblercmp(aptr, bptr) == GREATER)
        movetumbler(aptr, cptr);
    else
        movetumbler(bptr, cptr);
}

    void
functiontumbleradd(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
/* tumbler add is ~50% of cpu so has been */
/* tightened somewhat */
{
    if (iszerotumbler(bptr)) {
        movetumbler(aptr, cptr);
        return;

    } else if (iszerotumbler(aptr)) {
        movetumbler(bptr, cptr);
        return;

    } else if (aptr->sign == bptr->sign) {
        absadd(aptr, bptr, cptr);
        cptr->sign = aptr->sign;
/* absadd returns justified result so no need to justify */
/* I'm not so sure of the subtracts, they aren't used much */
/* 
 * if(cptr->mantissa[0] == 0){ partialtumblerjustify (cptr); } */
    } else if (abscmp(aptr, bptr) == GREATER) {
        strongsub(aptr, bptr, cptr);
        cptr->sign = aptr->sign;
        if (cptr->mantissa[0] == 0) {
            partialtumblerjustify(cptr);
        }
    } else {
        weaksub(bptr, aptr, cptr);
        cptr->sign = bptr->sign;
        if (cptr->mantissa[0] == 0) {
            partialtumblerjustify(cptr);
        }
    }
/* tumblercheck (cptr); */
/* 
 * if (cptr->sign) { L("TUMBLERADD NEGATIVE OUTPUT\n");
 * dumptumbler(cptr); L("\n"); } */
}

    void
tumblersub(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    Tumbler temp;

/* 
 * if(aptr->sign || bptr->sign) { L("TUMBLERSUB NEG IN \n");
 * dumptumbler(aptr); L(" "); dumptumbler(bptr);
 * L("\n"); } */
    if (iszerotumbler(bptr))
        movetumbler(aptr, cptr);

    else if (tumblereq(aptr, bptr))
        tumblerclear(cptr);

    else if (iszerotumbler(aptr)) {
        movetumbler(bptr, cptr);
        cptr->sign = !cptr->sign;

    } else {
        movetumbler(bptr, &temp);
        temp.sign = !temp.sign;
        tumbleradd(aptr, &temp, cptr);
    }
    tumblerjustify(cptr);
/* tumblercheck (cptr); */
/* 
 * if (cptr->sign) { L("TUMBLERSUB NEGATIVE OUTPUT\n");
 * dumptumbler(cptr); L("\n"); } */

}

#ifndef ExPeRiMENATL
#endif

    void
absadd(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    int i, j;
    //UNUSED int place;
    int temp;
    tdigit *ansmant;
    tdigit *bmant, *amant;
    Tumbler answer;

    i = j = 0;
    amant = aptr->mantissa;
    bmant = bptr->mantissa;
    answer.xvartumbler = 0;
    answer.varandnotfixed = 0;
    answer.sign = 0;
    ansmant = answer.mantissa;

    if (aptr->exp == bptr->exp) {
        answer.exp = aptr->exp;
        ansmant[0] = amant[0] + bmant[0];
        i = j = 1;

    } else if (aptr->exp > bptr->exp) {
        answer.exp = aptr->exp;
        temp = aptr->exp - bptr->exp;
        while (i < temp) {
            ansmant[j++] = amant[i++];
        }
        ansmant[j++] = amant[i++] + bmant[0];
        i = 1;

    } else {
        answer.exp = bptr->exp;
        temp = bptr->exp - aptr->exp;
        while (i <= temp) {
            ansmant[j++] = bmant[i++];
        }
    }

    while (j <= NPLACES - 1)
        ansmant[j++] = bmant[i++];

    movetumbler(&answer, cptr);
}

#ifdef  OlDVeRsIon

    void
absadd(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    int i, j;
    int place;
    int temp;
    tdigit *ansmant;
    tdigit *bmant, *amant;
    Tumbler answer;

    i = j = 0;
    amant = aptr->mantissa;
    bmant = bptr->mantissa;
    tumblerclear(&answer);
    ansmant = answer.mantissa;

    if (aptr->exp == bptr->exp) {
        answer.exp = aptr->exp;
        ansmant[0] = amant[0] + bmant[0];
        i = j = 1;

    } else if (aptr->exp > bptr->exp) {
        answer.exp = aptr->exp;
        temp = aptr->exp - bptr->exp;
        while (i < temp)
            ansmant[j++] = amant[i++];
        ansmant[j++] = amant[i++] + bmant[0];
        i = 1;

    } else {
        answer.exp = bptr->exp;
        temp = bptr->exp - aptr->exp;
        while (i <= temp)
            ansmant[j++] = bmant[i++];
    }

    while (j <= NPLACES - 1)
        ansmant[j++] = bmant[i++];

    movetumbler(&answer, cptr);
}

#endif

    void
strongsub(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    Tumbler answer;
    int i, j;

    tumblerclear(&answer);
    if (tumblereq(aptr, bptr)) {
        movetumbler(&answer, cptr);
        return;
    }

    if (bptr->exp < aptr->exp) {
        movetumbler(aptr, cptr);
        return;
    }

    answer.exp = aptr->exp;
    for (i = 0; aptr->mantissa[i] == bptr->mantissa[i]; ++i) {
        --answer.exp;
        if (i >= NPLACES) {
            movetumbler(&answer, cptr);
            return;
        }
    }

    answer.mantissa[0] = aptr->mantissa[i] - bptr->mantissa[i];
    if (++i >= NPLACES) {
        movetumbler(&answer, cptr);
        return;
    }

    for (j = 1; j < NPLACES && i < NPLACES;)
        answer.mantissa[j++] = aptr->mantissa[i++];

    movetumbler(&answer, cptr);
}

    void
weaksub(
    Tumbler *aptr,
    Tumbler *bptr,
    Tumbler *cptr)
{
    Tumbler answer;
    int i;
    int expdiff;

    tumblerclear(&answer);
    if (tumblereq(aptr, bptr)) {
        movetumbler(&answer, cptr);
        return;
    }

    answer.exp = aptr->exp;
    expdiff = aptr->exp - bptr->exp;

    for (i = 0; i < expdiff; ++i) {
        answer.mantissa[i] = aptr->mantissa[i];
        if (i >= NPLACES) {
            movetumbler(&answer, cptr);
            return;
        }
    }

    answer.mantissa[i] = aptr->mantissa[i] - bptr->mantissa[0];
    movetumbler(&answer, cptr);
}

    int
tumblerintdiff(
    Tumbler *aptr,
    Tumbler *bptr)
{
    Tumbler c;

    tumblersub(aptr, bptr, &c);
    return c.mantissa[0];
}

    void
tumblerincrement(
    Tumbler *aptr,
    int      rightshift,
    int      bint,
    Tumbler *cptr)
{
    int idx;

    if (iszerotumbler(aptr)) {
        tumblerclear(cptr);
        cptr->exp = -rightshift;
        cptr->mantissa[0] = bint;
        return;
    }

    if (aptr != cptr)
        movetumbler(aptr, cptr);

    for (idx = NPLACES; aptr->mantissa[--idx] == 0 && idx > 0;)
        ;

    if (idx + rightshift >= NPLACES) {
#ifndef DISTRIBUTION
        dumptumbler(aptr);
        L(" idx = %d  rightshift = %d\n", idx, rightshift);
        assert(0); // tumblerincrement overflow
#else
        assert(0);
#endif
    }

    cptr->mantissa[idx + rightshift] += bint;
    tumblerjustify(cptr);
}

    void
tumblertruncate(
    Tumbler *aptr,
    int      bint,
    Tumbler *cptr)
{
    Tumbler answer;
    int i;

    movetumbler(aptr, &answer);
    for (i = answer.exp; i < 0 && bint > 0; ++i, --bint)
        ;

    if (bint <= 0)
        tumblerclear(&answer);
    else
        for (; bint < NPLACES; ++bint)
            answer.mantissa[bint] = 0;

    tumblerjustify(&answer);
    movetumbler(&answer, cptr);
}

    void
prefixtumbler(
    Tumbler *aptr,
    int      bint,
    Tumbler *cptr)
{
    Tumbler temp1, temp2;

    tumblerclear(&temp1);
    temp1.mantissa[0] = bint;
    movetumbler(aptr, &temp2);

    if (!iszerotumbler(&temp2))        /* yuckh! */
        temp2.exp -= 1;

    tumbleradd(&temp1, &temp2, cptr);
}

/* 
 * beheadtumbler (aptr, bptr) tumbler *aptr, *bptr; { tumbler temp; int i;
 * 
 * movetumbler (aptr, &temp); if (temp.exp < 0) ++temp.exp; else { for (i =
 * 0; i < NPLACES-1; ++i) temp.mantissa[i] = temp.mantissa[i+1];
 * temp.mantissa[NPLACES-1] = 0; } tumblerjustify (&temp); movetumbler
 * (&temp, bptr); } */

    void
beheadtumbler(
    Tumbler *aptr,
    Tumbler *bptr)
{
    Tumbler temp;

    movetumbler(aptr, &temp);
    ++temp.exp;

    if (aptr->exp == 0)
        temp.mantissa[0] = 0;

    tumblerjustify(&temp);
    movetumbler(&temp, bptr);
}

    void
docidandvstream2tumbler(
    Tumbler *docid,
    Tumbler *vstream,
    Tumbler *tumbleptr)
{
    int i, j;

    movetumbler(docid, tumbleptr);
    for (i = NPLACES - 1; i >= 0; i--) {
        if (tumbleptr->mantissa[i]) {
            ++i;
            break;
        }
    }
    for (j = 0; i < NPLACES && j < NPLACES;)
        tumbleptr->mantissa[++i] = vstream->mantissa[j++];
}

---