/** 

 * XML Security Library (http://www.aleksey.com/xmlsec).

 *

 * Big Numbers.

 *

 * This is free software; see Copyright file in the source

 * distribution for preciese wording.

 * 

 * Copyright (C) 2002-2003 Aleksey Sanin <aleksey@aleksey.com>

 * Copyright (C) 2003 Cordys R&D BV, All rights reserved.

 * Portion Copyright © 2009 Nokia Corporation and/or its subsidiary(-ies). All rights reserved. 

 */

#include "xmlsec_globals.h" 

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <libxml2_tree.h>

#include <libxml2_globals.h>

#include "xmlsec_xmlsec.h"

#include "xmlsec_xmltree.h"

#include "xmlsec_base64.h"

#include "xmlsec_bn.h"

#include "xmlsec_errors.h"

/* table for converting hex digits back to bytes */

static const int xmlSecBnLookupTable[] =

{

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

     0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1,

    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1

};

static const char xmlSecBnRevLookupTable[] = 

{ 

    '0', '1', '2', '3', '4', '5', '6', '7', 

    '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' 

};

/*****************************************************************************

 *

 * xmlSecBn

 *

 ****************************************************************************/

/**

 * xmlSecBnCreate:

 * @size:	the initial allocated BN size.

 *

 * Creates a new BN object. Caller is responsible for destroying it

 * by calling @xmlSecBnDestroy function.

 *

 * Returns the newly BN or a NULL if an error occurs.

 */

EXPORT_C

xmlSecBnPtr 

xmlSecBnCreate(xmlSecSize size) {

    return(xmlSecBufferCreate(size));

}

/**

 * xmlSecBnDestroy:

 * @bn:		the pointer to BN.

 *

 * Destroys @bn object created with @xmlSecBnCreate function.

 */

EXPORT_C

void 

xmlSecBnDestroy(xmlSecBnPtr bn) {

    xmlSecBufferDestroy(bn);

}

/**

 * xmlSecBnInitialize:

 * @bn:		the pointer to BN.

 * @size:	the initial allocated BN size.

 *

 * Initializes a BN object. Caller is responsible for destroying it

 * by calling @xmlSecBnFinalize function.

 *

 * Returns 0 on success or a negative value if an error occurs.

 */

EXPORT_C

int 

xmlSecBnInitialize(xmlSecBnPtr bn, xmlSecSize size) {

    return(xmlSecBufferInitialize(bn, size));

}

/**

 * xmlSecBnFinalize:

 * @bn:		the pointer to BN.

 *

 * Destroys @bn object created with @xmlSecBnInitialize function.

 */

EXPORT_C

void 

xmlSecBnFinalize(xmlSecBnPtr bn) {

    xmlSecBufferFinalize(bn);

}

/**

 * xmlSecBnGetData:

 * @bn:		the pointer to BN.

 *

 * Gets pointer to the binary @bn representation.

 * 

 * Returns pointer to binary BN data or NULL if an error occurs.

 */

EXPORT_C

xmlSecByte* 

xmlSecBnGetData(xmlSecBnPtr bn) {

    return(xmlSecBufferGetData(bn));

}

/**

 * xmlSecBnSetData:

 * @bn:		the pointer to BN.

 * @data:	the pointer to new BN binary data.

 * @size:	the size of new BN data.

 *

 * Sets the value of @bn to @data.

 *

 * Returns 0 on success or a negative value if an error occurs.

 */

EXPORT_C

int 

xmlSecBnSetData(xmlSecBnPtr bn, const xmlSecByte* data, xmlSecSize size) {

    return(xmlSecBufferSetData(bn, data, size));

}

/**

 * xmlSecBnGetSize:

 * @bn:		the pointer to BN.

 *

 * Gets the size of binary data in @bn.

 *

 * Returns the size of binary data.

 */

EXPORT_C

xmlSecSize 

xmlSecBnGetSize(xmlSecBnPtr bn) {

    return(xmlSecBufferGetSize(bn));

}

/**

 * xmlSecBnZero:

 * @bn:		the pointer to BN.

 *

 * Sets the value of @bn to zero.

 */

EXPORT_C

void 

xmlSecBnZero(xmlSecBnPtr bn) {

    xmlSecBufferEmpty(bn);

}

/**

 * xmlSecBnFromString:

 * @bn:		the pointer to BN.

 * @str:	the string with BN.

 * @base:	the base for @str.

 *

 * Reads @bn from string @str assuming it has base @base.

 *

 * Returns 0 on success or a negative value if an error occurs.

 */

EXPORT_C

int 

xmlSecBnFromString(xmlSecBnPtr bn, const xmlChar* str, xmlSecSize base) {

    xmlSecSize i, len, size;

    xmlSecByte ch;

    xmlSecByte* data;

    int positive;

    int nn;

    int ret;

    xmlSecAssert2(bn != NULL, -1);

    xmlSecAssert2(str != NULL, -1);

    xmlSecAssert2(base > 1, -1);

    xmlSecAssert2(base <= sizeof(xmlSecBnRevLookupTable), -1);

    /* trivial case */

    len = xmlStrlen(str);

    if(len == 0) {

        return(0);

    }

    /* The result size could not exceed the input string length

     * because each char fits inside a byte in all cases :)

     * In truth, it would be likely less than 1/2 input string length

     * because each byte is represented by 2 chars. If needed, 

     * buffer size would be increased by Mul/Add functions.

     * Finally, we can add one byte for 00 or 10 prefix.

     */

    ret = xmlSecBufferSetMaxSize(bn, xmlSecBufferGetSize(bn) + len / 2 + 1 + 1);

    if(ret < 0) {

        xmlSecError(XMLSEC_ERRORS_HERE,

		        NULL,

		        "xmlSecBnRevLookupTable",

		        XMLSEC_ERRORS_R_XMLSEC_FAILED,

		        "size=%d", len / 2 + 1);

        return (-1);

    }

    /* figure out if it is positive or negative number */

    positive = 1;

    i = 0;

    while(i < len) {

        ch = str[i++];

        /* skip spaces */

        if(isspace(ch)) {

	        continue;

        } 

        /* check if it is + or - */

        if(ch == '+') {

            positive = 1;

            break;

        } else if(ch == '-') {

            positive = 0;

            break;

        }

        /* otherwise, it must be start of the number */

        nn = xmlSecBnLookupTable[ch];

        if((nn >= 0) && ((xmlSecSize)nn < base)) {

            xmlSecAssert2(i > 0, -1);

            /* no sign, positive by default */

            positive = 1;

            --i; /* make sure that we will look at this character in next loop */

            break;

        } else {

	        xmlSecError(XMLSEC_ERRORS_HERE,

		        NULL,

		        NULL,

		        XMLSEC_ERRORS_R_INVALID_DATA,

		        "char=%c;base=%d", 

		        ch, base);

    	        return (-1);

        }

    }

    /* now parse the number itself */

    while(i < len) {

        ch = str[i++];

        if(isspace(ch)) {

	        continue;

        }

        nn = xmlSecBnLookupTable[ch];

        if((nn < 0) || ((xmlSecSize)nn > base)) {

	        xmlSecError(XMLSEC_ERRORS_HERE,

		        NULL,

		        NULL,

		        XMLSEC_ERRORS_R_INVALID_DATA,

		        "char=%c;base=%d", 

		        ch, base);

    	        return (-1);

        }

        ret = xmlSecBnMul(bn, base);

        if(ret < 0) {

	        xmlSecError(XMLSEC_ERRORS_HERE,

		        NULL,

		        "xmlSecBnMul",

		        XMLSEC_ERRORS_R_XMLSEC_FAILED,

		        "base=%d", base);

	        return (-1);

        }

        ret = xmlSecBnAdd(bn, nn);

        if(ret < 0) {

	        xmlSecError(XMLSEC_ERRORS_HERE,

		        NULL,

		        "xmlSecBnAdd",

		        XMLSEC_ERRORS_R_XMLSEC_FAILED,

		        "base=%d", base);

	        return (-1);

}	

    }

    /* check if we need to add 00 prefix, do this for empty bn too */

    data = xmlSecBufferGetData(bn);

    size = xmlSecBufferGetSize(bn);

    if(((size > 0) && (data[0] > 127)) || (size == 0))  {

        ch = 0;

        ret = xmlSecBufferPrepend(bn, &ch, 1);

        if(ret < 0) {

            xmlSecError(XMLSEC_ERRORS_HERE,

                NULL,

                "xmlSecBufferPrepend",

                XMLSEC_ERRORS_R_XMLSEC_FAILED,

                "base=%d", base);

            return (-1);

        }

    }

    /* do 2's compliment and add 1 to represent negative value */

    if(positive == 0) {

        data = xmlSecBufferGetData(bn);

        size = xmlSecBufferGetSize(bn);

        for(i = 0; i < size; ++i) {

            data[i] ^= 0xFF;

        }

        ret = xmlSecBnAdd(bn, 1);

        if(ret < 0) {

            xmlSecError(XMLSEC_ERRORS_HERE,

                NULL,

                "xmlSecBnAdd",

                XMLSEC_ERRORS_R_XMLSEC_FAILED,

                "base=%d", base);

            return (-1);

        }

    }

    return(0);

}

/**

 * xmlSecBnToString:

 * @bn:		the pointer to BN.

 * @base:	the base for returned string.

 *

 * Writes @bn to string with base @base. Caller is responsible for 

 * freeing returned string with @xmlFree.

 *

 * Returns the string represenataion if BN or a NULL if an error occurs.

 */

EXPORT_C

xmlChar* 

xmlSecBnToString(xmlSecBnPtr bn, xmlSecSize base) {

    xmlSecBn bn2;

    int positive = 1;

    xmlChar* res;

    xmlSecSize i, len, size;

    xmlSecByte* data;

    int ret;

    int nn;

    xmlChar ch;

    xmlSecAssert2(bn != NULL, NULL);

    xmlSecAssert2(base > 1, NULL);

    xmlSecAssert2(base <= sizeof(xmlSecBnRevLookupTable), NULL);

    /* copy bn */

    data = xmlSecBufferGetData(bn);

    size = xmlSecBufferGetSize(bn);

    ret = xmlSecBnInitialize(&bn2, size);

    if(ret < 0) {

        xmlSecError(XMLSEC_ERRORS_HERE,

            NULL,

            "xmlSecBnCreate",

            XMLSEC_ERRORS_R_XMLSEC_FAILED,

            "size=%d", size);

        return (NULL);

    }

    ret = xmlSecBnSetData(&bn2, data, size);

    if(ret < 0) {

        xmlSecError(XMLSEC_ERRORS_HERE,

            NULL,

            "xmlSecBnSetData",

            XMLSEC_ERRORS_R_XMLSEC_FAILED,

            "size=%d", size);

        xmlSecBnFinalize(&bn2);

        return (NULL);

    }

    /* check if it is a negative number or not */

    data = xmlSecBufferGetData(&bn2);

    size = xmlSecBufferGetSize(&bn2);

    if((size > 0) && (data[0] > 127)) {

        /* subtract 1 and do 2's compliment */

        ret = xmlSecBnAdd(&bn2, -1);

        if(ret < 0) {

            xmlSecError(XMLSEC_ERRORS_HERE,

                        NULL,

                        "xmlSecBnAdd",

                        XMLSEC_ERRORS_R_XMLSEC_FAILED,

                        "size=%d", size);

            xmlSecBnFinalize(&bn2);

            return (NULL);

        }

        for(i = 0; i < size; ++i) {

            data[i] ^= 0xFF;

        }

        positive = 0;

    } else {

        positive = 1;

    }

    /* Result string len is

     *	    len = log base (256) * <bn size>

     * Since the smallest base == 2 then we can get away with 

     *	    len = 8 * <bn size>

     */

    len = 8 * size + 1 + 1;

    res = (xmlChar*)xmlMalloc(len + 1);

    if(res == NULL) {

        xmlSecError(XMLSEC_ERRORS_HERE,

		            NULL,

		            NULL,

		            XMLSEC_ERRORS_R_MALLOC_FAILED,

		            "len=%d", len);

        xmlSecBnFinalize(&bn2);

        return (NULL);

    }

    memset(res, 0, len + 1);

            xmlSecError(XMLSEC_ERRORS_HERE,

                        NULL,

                        "xmlSecBnDiv",

                        XMLSEC_ERRORS_R_XMLSEC_FAILED,

                        "base=%d", base);

            xmlFree(res);

            xmlSecBnFinalize(&bn2);

            return (NULL);

        res[i] = xmlSecBnRevLookupTable[nn];

    /* we might have '0' at the beggining, remove it but keep one zero */

    for(len = i; (len > 1) && (res[len - 1] == '0'); len--)

        {

        };

    res[len] = '\0';

    /* add "-" for negative numbers */

    if(positive == 0) {

        res[len] = '-';

        res[++len] = '\0';

    }

    /* swap the string because we wrote it in reverse order */

    for(i = 0; i < len / 2; i++) {

        ch = res[i];

        res[i] = res[len - i - 1];

        res[len - i - 1] = ch;

    }

    xmlSecBnFinalize(&bn2);

    return(res);

}

/**

 * xmlSecBnFromHexString:

 * @bn:		the pointer to BN.

 * @str:	the string with BN.

 *

 * Reads @bn from hex string @str.

 *

 * Returns 0 on success or a negative value if an error occurs.

 */

EXPORT_C

int 

xmlSecBnFromHexString(xmlSecBnPtr bn, const xmlChar* str) {

    return(xmlSecBnFromString(bn, str, 16));

}

/**

 * xmlSecBnToHexString:

 * @bn:		the pointer to BN.

 *

 * Writes @bn to hex string. Caller is responsible for 

 * freeing returned string with @xmlFree.

 *

 * Returns the string represenataion if BN or a NULL if an error occurs.

 */

EXPORT_C

xmlChar* 

xmlSecBnToHexString(xmlSecBnPtr bn) {

    return(xmlSecBnToString(bn, 16));

}

/**

 * xmlSecBnFromDecString:

 * @bn:		the pointer to BN.

 * @str:	the string with BN.

 *

 * Reads @bn from decimal string @str.

 *

 * Returns 0 on success or a negative value if an error occurs.

 */

EXPORT_C

int 

xmlSecBnFromDecString(xmlSecBnPtr bn, const xmlChar* str) {

    return(xmlSecBnFromString(bn, str, 10));

}

/**

 * xmlSecBnToDecString:

 * @bn:		the pointer to BN.

 *