| /********************************************************************** |
| // @@@ START COPYRIGHT @@@ |
| // |
| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| // |
| // @@@ END COPYRIGHT @@@ |
| **********************************************************************/ |
| /* -*-C++-*- |
| ***************************************************************************** |
| * |
| * File: BigNumHelper.cpp |
| * Description: Implementation of class BigNumHelper |
| * Created: 03/29/99 |
| * Language: C++ |
| * |
| * |
| * |
| * |
| ***************************************************************************** |
| */ |
| #include "Platform.h" |
| #include <math.h> |
| #define MathCeil(op,err) ceil(op) |
| |
| #include "str.h" |
| #include "BigNumHelper.h" |
| |
| static const unsigned short powersOfTen[] = {10, // 10^1 |
| 100, // 10^2 |
| 1000, // 10^3 |
| 10000}; // 10^4 |
| |
| static const unsigned short powersOfTenInBigNumForm[] = {0x0001, 0x0000, 0x0000, 0x0000, // 10^0 |
| 0x000A, 0x0000, 0x0000, 0x0000, // 10^1 |
| 0x0064, 0x0000, 0x0000, 0x0000, // 10^2 |
| 0x03E8, 0x0000, 0x0000, 0x0000, // 10^3 |
| 0x2710, 0x0000, 0x0000, 0x0000, // 10^4 |
| 0x86A0, 0x0001, 0x0000, 0x0000, // 10^5 |
| 0x4240, 0x000F, 0x0000, 0x0000, // 10^6 |
| 0x9680, 0x0098, 0x0000, 0x0000, // 10^7 |
| 0xE100, 0x05F5, 0x0000, 0x0000, // 10^8 |
| 0xCA00, 0x3B9A, 0x0000, 0x0000, // 10^9 |
| 0xE400, 0x540B, 0x0002, 0x0000, // 10^10 |
| 0xE800, 0x4876, 0x0017, 0x0000, // 10^11 |
| 0x1000, 0xD4A5, 0x00E8, 0x0000, // 10^12 |
| 0xA000, 0x4E72, 0x0918, 0x0000, // 10^13 |
| 0x4000, 0x107A, 0x5AF3, 0x0000, // 10^14 |
| 0x8000, 0xA4C6, 0x8D7E, 0x0003, // 10^15 |
| 0x0000, 0x6FC1, 0x86F2, 0x0023, // 10^16 |
| 0x0000, 0x5D8A, 0x4578, 0x0163, // 10^17 |
| 0x0000, 0xA764, 0xB6B3, 0x0DE0, // 10^18 |
| 0x0000, 0x89E8, 0x2304, 0x8AC7};// 10^19 |
| |
| |
| // The following method adds two Big Nums (without signs). |
| |
| short BigNumHelper::AddHelper(Lng32 dataLength, |
| char * leftData, |
| char * rightData, |
| char * resultData) |
| { |
| |
| // Recast from bytes to unsigned shorts. |
| Lng32 dataLengthInShorts = dataLength/2; |
| unsigned short * leftDataInShorts = (unsigned short *) leftData; |
| unsigned short * rightDataInShorts = (unsigned short *) rightData; |
| unsigned short * resultDataInShorts = (unsigned short *) resultData; |
| |
| #ifdef NA_LITTLE_ENDIAN |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short remainder; |
| unsigned short carry; |
| } tempParts; |
| }; |
| #else |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short carry; |
| unsigned short remainder; |
| } tempParts; |
| }; |
| #endif |
| |
| tempParts.carry = 0; |
| for (Lng32 j = 0; j < dataLengthInShorts; j++) |
| { |
| temp = ((ULng32) leftDataInShorts[j]) + rightDataInShorts[j] + tempParts.carry; |
| resultDataInShorts[j] = tempParts.remainder; |
| } |
| |
| return 0; |
| |
| } |
| |
| |
| // The following method subtracts one Big Num from another (without signs). |
| |
| short BigNumHelper::SubHelper(Lng32 dataLength, |
| char * leftData, |
| char * rightData, |
| char * resultData) |
| { |
| |
| // Recast from bytes to unsigned shorts. |
| Lng32 dataLengthInShorts = dataLength/2; |
| unsigned short * leftDataInShorts = (unsigned short *) leftData; |
| unsigned short * rightDataInShorts = (unsigned short *) rightData; |
| unsigned short * resultDataInShorts = (unsigned short *) resultData; |
| |
| // Check if left is smaller than right, and |
| // if so, switch left with right. |
| unsigned short * left = leftDataInShorts; |
| unsigned short * right = rightDataInShorts; |
| |
| Int32 neg = 0; |
| Lng32 j = 0; |
| for (j = 0; j < dataLengthInShorts; j++) { |
| if (rightDataInShorts[j] > leftDataInShorts[j]) |
| neg = -1; |
| else if (rightDataInShorts[j] < leftDataInShorts[j]) |
| neg = 0; |
| } |
| |
| if (neg == -1) |
| { |
| left = rightDataInShorts; |
| right = leftDataInShorts; |
| } |
| |
| short carry = 0; |
| Lng32 temp; |
| |
| #ifdef NA_LITTLE_ENDIAN |
| union { |
| ULng32 temp1; |
| struct { |
| unsigned short remainder; |
| unsigned short filler; |
| } tempParts; |
| }; |
| #else |
| union { |
| ULng32 temp1; |
| struct { |
| unsigned short filler; |
| unsigned short remainder; |
| } tempParts; |
| }; |
| #endif |
| |
| for (j = 0; j < dataLengthInShorts; j++) |
| { |
| temp = ((Lng32) left[j]) - right[j] + carry; |
| temp1 = temp + (Lng32) USHRT_MAX + 1; // Note that USHRT_MAX + 1 = 2^16. |
| resultDataInShorts[j] = tempParts.remainder; |
| carry = ( temp < 0 ? -1 : 0); |
| } |
| |
| return neg; |
| |
| } |
| |
| // The following method multiplies two Big Nums (without signs). |
| // The assumption is that the result is big enough to hold the |
| // product. |
| |
| short BigNumHelper::MulHelper(Lng32 resultLength, |
| Lng32 leftLength, |
| Lng32 rightLength, |
| char * leftData, |
| char * rightData, |
| char * resultData) |
| { |
| |
| // Recast from bytes to unsigned shorts. |
| unsigned short * leftDataInShorts = (unsigned short *) leftData; |
| unsigned short * rightDataInShorts = (unsigned short *) rightData; |
| unsigned short * resultDataInShorts = (unsigned short *) resultData; |
| |
| // Set result to zero. |
| for (Int32 k = 0; k < resultLength/2; k++) |
| resultDataInShorts[k] = 0; |
| |
| // Skip trailing zeros in the left and the right argument |
| // to shorten the nested loop that appears later. |
| Lng32 rightEndInShorts = rightLength/2 - 1; |
| while (!rightDataInShorts[rightEndInShorts] && rightEndInShorts >= 0) |
| rightEndInShorts--; |
| if (rightEndInShorts < 0) |
| return 0; |
| |
| Lng32 leftEndInShorts = leftLength/2 - 1; |
| while (!leftDataInShorts[leftEndInShorts] && leftEndInShorts >= 0) |
| leftEndInShorts--; |
| if (leftEndInShorts < 0) |
| return 0; |
| |
| // Int64 temp; |
| // unsigned long * remainder = (unsigned long *) &temp; |
| // unsigned long * carry = remainder + 1; |
| |
| #ifdef NA_LITTLE_ENDIAN |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short remainder; |
| unsigned short carry; |
| } tempParts; |
| }; |
| #else |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short carry; |
| unsigned short remainder; |
| } tempParts; |
| }; |
| #endif |
| |
| Lng32 pos; |
| for (Lng32 j = 0; j <= rightEndInShorts; j++) |
| { |
| tempParts.carry = 0; |
| pos = j; |
| for (Lng32 i = 0; i <= leftEndInShorts; i++, pos++) |
| { |
| temp = ((ULng32) leftDataInShorts[i]) * rightDataInShorts[j] + resultDataInShorts[pos] + tempParts.carry; |
| resultDataInShorts[pos] = tempParts.remainder; |
| } |
| |
| if (tempParts.carry) |
| resultDataInShorts[pos] = tempParts.carry; |
| } |
| |
| return 0; |
| |
| } |
| |
| // The following method divides one Big Num by another (both without signs), |
| // only if the divisor fits in an unsigned short. It returns 1 if there is |
| // a remainder, 0 if there is no remainder, and -1 if there is an error. |
| |
| short BigNumHelper::SimpleDivHelper(Lng32 dividendLength, |
| Lng32 divisorLength, |
| char * dividendData, |
| char * divisorData, |
| char * quotientData) |
| |
| { |
| // Recast from bytes to unsigned shorts. |
| Lng32 dividendLengthInShorts = dividendLength/2; |
| Lng32 divisorLengthInShorts = divisorLength/2; |
| unsigned short * dividendDataInShorts = (unsigned short *) dividendData; |
| unsigned short * divisorDataInShorts = (unsigned short *) divisorData; |
| unsigned short * quotientDataInShorts = (unsigned short *) quotientData; |
| |
| if (divisorLengthInShorts > 1) |
| return -1; // Error. |
| |
| unsigned short remainder = 0; |
| union { |
| ULng32 temp; |
| unsigned short temp1[2]; |
| }; |
| |
| for (Int32 j = dividendLengthInShorts - 1; j >= 0; j--) |
| { |
| |
| #ifdef NA_LITTLE_ENDIAN |
| temp1[0] = dividendDataInShorts[j]; |
| temp1[1] = remainder; |
| #else |
| temp1[1] = dividendDataInShorts[j]; |
| temp1[0] = remainder; |
| #endif |
| |
| quotientDataInShorts[j] = (unsigned short) (temp / divisorDataInShorts[0]); |
| remainder = (unsigned short ) (temp % divisorDataInShorts[0]); |
| } |
| |
| if (remainder != 0) |
| return 1; |
| else |
| return 0; |
| } |
| |
| // The following division algorithm is based on the one |
| // in Knuth's book on Seminumerical Algorithms, 2nd edition. |
| // Some of the steps in our implementation are more optimized |
| // to take advantage of base 2^16. |
| // |
| // The method divides one Big Num by another (both without signs). |
| // It returns 1 if there is a remainder, 0 if there is no remainder. |
| // (Note: there does not seem to be a need yet to actually calculate |
| // the remainder. If such a need arises in the future, the method |
| // should be changed accordingly.) |
| // |
| // The caller should pass tempData, which must point to memory |
| // (aligned on 2-byte boundary) of size (in bytes) : |
| // 3 * dividendLength + 6 |
| // to be used for temporary calculations. |
| |
| short BigNumHelper::DivHelper(Lng32 dividendLength, |
| Lng32 divisorLength, |
| char * dividendData, |
| char * divisorData, |
| char * quotientData, |
| char * tempData) |
| { |
| // Recast from bytes to unsigned shorts. |
| Lng32 dividendLengthInShorts = dividendLength/2; |
| Lng32 divisorLengthInShorts = divisorLength/2; |
| unsigned short * divisorDataInShorts = (unsigned short *) divisorData; |
| unsigned short * quotientDataInShorts = (unsigned short *) quotientData; |
| |
| char * tempDividendData = tempData; |
| unsigned short * tempDividendDataInShorts = (unsigned short *) tempDividendData; |
| unsigned short * tempDivisorDataInShorts = tempDividendDataInShorts + dividendLengthInShorts + 1; |
| unsigned short * tempDivisorData1InShorts = tempDivisorDataInShorts + divisorLengthInShorts + 1; |
| char * tempDivisorData = (char *) tempDivisorDataInShorts; |
| char * tempDivisorData1 = (char *) tempDivisorData1InShorts; |
| |
| // Begin normalizing step. |
| |
| #ifdef NA_LITTLE_ENDIAN |
| |
| if (divisorDataInShorts[divisorLengthInShorts - 1] <= UCHAR_MAX) { // Note that UCHAR_MAX = 0xFF |
| |
| // Multiply divisorData by 0x100 (= UCHAR_MAX + 1) and store in tempDivisorData. |
| // Note that the size of tempDivisorData is 2 bytes more than divisorData. |
| tempDivisorData[0] = 0; |
| Int32 i; |
| for (i = 0; i < divisorLength; i++) |
| tempDivisorData[i+1] = divisorData[i]; |
| tempDivisorData[divisorLength + 1] = 0; |
| |
| // Multiply dividendData by 0x100 and store in tempDividendData. |
| // Note that the size of tempDividendData is 2 bytes more than dividendData. |
| tempDividendData[0] = 0; |
| for (i = 0; i < dividendLength; i++) |
| tempDividendData[i+1] = dividendData[i]; |
| tempDividendData[dividendLength + 1] = 0; |
| |
| } |
| else { |
| Int32 i; |
| // Multiply divisorData by 1 and store in tempDivisorData. |
| for (i = 0; i < divisorLength; i++) |
| tempDivisorData[i] = divisorData[i]; |
| tempDivisorDataInShorts[divisorLengthInShorts] = 0; |
| |
| // Multiply dividendData by 1 and store in tempDividendData. |
| for (i = 0; i < dividendLength; i++) |
| tempDividendData[i] = dividendData[i]; |
| tempDividendDataInShorts[dividendLengthInShorts] = 0; |
| |
| } |
| |
| #else |
| |
| if (divisorDataInShorts[divisorLengthInShorts - 1] <= UCHAR_MAX) { |
| |
| Int32 i = 0; |
| |
| // Multiply divisorData by 0x100 and store in tempDivisorData. |
| tempDivisorData[1] = 0; |
| for (i = 0; i < divisorLengthInShorts; i++) { |
| tempDivisorData[2*i+3] = divisorData[2*i]; |
| tempDivisorData[2*i] = divisorData[2*i+1]; |
| } |
| tempDivisorData[divisorLength] = 0; |
| |
| // Multiply dividendData by 0x100 and store in tempDividendData. |
| tempDividendData[1] = 0; |
| for (i = 0; i < dividendLengthInShorts; i++) { |
| tempDividendData[2*i+3] = dividendData[2*i]; |
| tempDividendData[2*i] = dividendData[2*i+1]; |
| } |
| tempDividendData[dividendLength] = 0; |
| |
| } |
| |
| else { |
| |
| Int32 i = 0; |
| |
| // Multiply divisorData by 1 and store in tempDivisorData. |
| for (i = 0; i < divisorLength; i++) |
| tempDivisorData[i] = divisorData[i]; |
| tempDivisorDataInShorts[divisorLengthInShorts] = 0; |
| |
| // Multiply dividendData by 1 and store in tempDividendData. |
| for (i = 0; i < dividendLength; i++) |
| tempDividendData[i] = dividendData[i]; |
| tempDividendDataInShorts[dividendLengthInShorts] = 0; |
| |
| } |
| |
| #endif |
| // End normalizing step. |
| |
| // Set the quotient to zero. |
| Int32 j = 0; |
| for (j = 0; j < dividendLengthInShorts ; j++) |
| quotientDataInShorts[j] = 0; |
| |
| unsigned short q; |
| |
| union { |
| ULng32 temp1; |
| unsigned short temp2[2]; |
| }; |
| |
| union { |
| Int64 temp3; |
| unsigned short temp4[4]; |
| }; |
| |
| Int32 m = dividendLengthInShorts - divisorLengthInShorts; |
| Lng32 dividendPosInShorts = dividendLengthInShorts; |
| |
| // The main loop for division. |
| for (j = 0; j <= m; j++) { |
| |
| #ifdef NA_LITTLE_ENDIAN |
| temp4[3] = 0; |
| temp4[2] = tempDividendDataInShorts[dividendPosInShorts]; |
| temp4[1] = tempDividendDataInShorts[dividendPosInShorts - 1]; |
| temp4[0] = tempDividendDataInShorts[dividendPosInShorts - 2]; |
| temp2[1] = tempDivisorDataInShorts[divisorLengthInShorts - 1]; |
| temp2[0] = tempDivisorDataInShorts[divisorLengthInShorts - 2]; |
| #else |
| temp4[0] = 0; |
| temp4[1] = tempDividendDataInShorts[dividendPosInShorts]; |
| temp4[2] = tempDividendDataInShorts[dividendPosInShorts - 1]; |
| temp4[3] = tempDividendDataInShorts[dividendPosInShorts - 2]; |
| temp2[0] = tempDivisorDataInShorts[divisorLengthInShorts - 1]; |
| temp2[1] = tempDivisorDataInShorts[divisorLengthInShorts - 2]; |
| #endif |
| |
| q = (unsigned short) (temp3 / temp1); |
| |
| if (q == 0) |
| { |
| if (tempDividendDataInShorts[dividendLengthInShorts - j] == |
| tempDivisorDataInShorts[divisorLengthInShorts - 1]) |
| |
| q = USHRT_MAX; // Note that USHRT_MAX is the largest digit in base 2^16. |
| } |
| |
| BigNumHelper::MulHelper(divisorLength + 2, |
| divisorLength, |
| 2, |
| tempDivisorData, |
| (char *) &q, |
| tempDivisorData1); |
| |
| Int32 neg = BigNumHelper::SubHelper(divisorLength + 2, |
| (char *) &tempDividendDataInShorts[dividendPosInShorts - divisorLengthInShorts], |
| tempDivisorData1, |
| (char *) &tempDividendDataInShorts[dividendPosInShorts - divisorLengthInShorts]); |
| |
| if (neg) { |
| |
| // q is too large. |
| q--; |
| |
| // Add back by subtracting the result of the last subtraction (which is |
| // actually negative) from tempDividendData. We ignore the return code of |
| // SubHelper(), because we know the result is always positive. |
| BigNumHelper::SubHelper(divisorLength + 2, |
| tempDivisorData, |
| (char *) &tempDividendDataInShorts[dividendPosInShorts - divisorLengthInShorts], |
| (char *) &tempDividendDataInShorts[dividendPosInShorts - divisorLengthInShorts]); |
| } |
| |
| quotientDataInShorts[dividendPosInShorts - divisorLengthInShorts] = q; |
| |
| dividendPosInShorts--; |
| |
| } // for j |
| |
| // Check whether there was any remainder. |
| for (j = 0; j < divisorLengthInShorts; j++) { |
| if (tempDividendDataInShorts[j] != 0) |
| return 1; |
| } |
| return 0; |
| |
| } |
| |
| // The following method converts a given Big Num (without sign) into |
| // its equivalent BCD string representation (with the more significant decimal |
| // digits in the lower addresses). |
| |
| short BigNumHelper::ConvBigNumToBcdHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData, |
| NAMemory * heap) |
| |
| { |
| // Recast from bytes to unsigned shorts. |
| Lng32 sourceLengthInShorts = sourceLength/2; |
| unsigned short * sourceDataInShorts = (unsigned short *) sourceData; |
| |
| unsigned short tempSourceDataInShortsBuf[128 / 2]; |
| unsigned short* tempSourceDataInShorts = tempSourceDataInShortsBuf; |
| |
| if (heap) |
| tempSourceDataInShorts = new (heap) unsigned short [sourceLength / 2]; |
| |
| Int32 i = 0; |
| for (i = 0; i < sourceLengthInShorts; i++) |
| tempSourceDataInShorts[i] = sourceDataInShorts[i]; |
| |
| // Initialize the BCD to zero. |
| for (i = 0; i < targetLength; i++) |
| targetData[i] = 0; |
| char * finalTargetData = targetData + targetLength - 1; |
| Lng32 finalTargetLength = 1; |
| |
| // Ignore trailing zeros in the Big Num. If all zeros, return. |
| Lng32 actualSourceLengthInShorts = sourceLengthInShorts; |
| while (!tempSourceDataInShorts[actualSourceLengthInShorts - 1] && actualSourceLengthInShorts > 0) |
| actualSourceLengthInShorts--; |
| if (!actualSourceLengthInShorts) { |
| if (heap) |
| NADELETEBASIC(tempSourceDataInShorts, (heap)); |
| return 0; |
| } |
| |
| union { |
| ULng32 temp; |
| unsigned short temp1[2]; |
| }; |
| |
| unsigned short remainder = 0; |
| |
| // Compute the final BCD as follows. Keep dividing the Big Num by 10^4 |
| // until the quotient becomes less than 10^4. At each iteration, compute |
| // the 4-digit BCD representation of the remainder, and append it to the |
| // left of the final BCD. For the final remainder, compute its BCD |
| // representation (which may be less than 4-digits) and append it to the |
| // left of the final BCD. |
| |
| finalTargetData++; |
| finalTargetLength = 0; |
| while ((actualSourceLengthInShorts != 1) || |
| (tempSourceDataInShorts[actualSourceLengthInShorts - 1] >= 10000)) { |
| |
| // Divide the Big Num by 10^4. It is more efficient to insert |
| // the division code than to call SimpleDivideHelper(); |
| Int32 j = 0; |
| for (j = actualSourceLengthInShorts - 1; j >= 0; j--) { |
| |
| #ifdef NA_LITTLE_ENDIAN |
| temp1[0] = tempSourceDataInShorts[j]; |
| temp1[1] = remainder; |
| #else |
| temp1[1] = tempSourceDataInShorts[j]; |
| temp1[0] = remainder; |
| #endif |
| |
| tempSourceDataInShorts[j] = (unsigned short) (temp / 10000); |
| remainder = (unsigned short) (temp % 10000); |
| } |
| if (!tempSourceDataInShorts[actualSourceLengthInShorts - 1]) |
| actualSourceLengthInShorts--; |
| |
| // Compute the BCD representation of the remainder and append to the |
| // left of the final BCD. |
| for (j = 0; j < 4; j++) { |
| if (finalTargetLength >= targetLength) { |
| if (heap) |
| NADELETEBASIC(tempSourceDataInShorts, (heap)); |
| return -1; |
| } |
| finalTargetData--; |
| finalTargetLength++; |
| finalTargetData[0] = remainder % 10; |
| remainder = remainder / 10; |
| } |
| } |
| |
| // Compute the BCD representation of the final remainder and append to the |
| // left of the final BCD. |
| remainder = tempSourceDataInShorts[0]; |
| while (remainder) { |
| if (finalTargetLength >= targetLength) { |
| if (heap) |
| NADELETEBASIC(tempSourceDataInShorts, (heap)); |
| return -1; |
| } |
| finalTargetData--; |
| finalTargetLength++; |
| finalTargetData[0] = remainder % 10; |
| remainder = remainder / 10; |
| } |
| |
| if (heap) |
| NADELETEBASIC(tempSourceDataInShorts, (heap)); |
| |
| return 0; |
| } |
| |
| // The following method converts a given BCD string representation (without sign, |
| // and with the more significant decimal digits in the lower addresses) |
| // into its equivalent Big Num representation. |
| |
| short BigNumHelper::ConvBcdToBigNumHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData) |
| |
| |
| { |
| // Recast from bytes to unsigned shorts. |
| Lng32 targetLengthInShorts = targetLength/2; |
| unsigned short * targetDataInShorts = (unsigned short *) targetData; |
| |
| // Initialize the Big Num to zero. |
| Int32 i = 0; |
| for (i = 0; i < targetLengthInShorts; i++) |
| targetDataInShorts[i] = 0; |
| Lng32 finalTargetLengthInShorts = 1; |
| |
| // Ignore leading zeros in BCD. If all zeros, return. |
| Lng32 zeros = 0; |
| while ((zeros < sourceLength) && !sourceData[zeros]) |
| zeros++; |
| if (zeros == sourceLength) |
| return 0; |
| |
| Int32 actualSourceLength = sourceLength - zeros; |
| char * actualSourceData = sourceData + zeros; |
| |
| |
| #ifdef NA_LITTLE_ENDIAN |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short remainder; |
| unsigned short carry; |
| } tempParts; |
| }; |
| #else |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short carry; |
| unsigned short remainder; |
| } tempParts; |
| }; |
| #endif |
| |
| // Compute the Big Num as follows. First, chunk up the BCD |
| // string into chunks of 4-digit unsigned short numbers. Iterate |
| // over these chunks, and at each iteration, multiply the current |
| // Big Num by 10^4 and then add the numeric value of this chunk |
| // to it. |
| for (i = 0; i < actualSourceLength; i += 4) { |
| |
| // Compute the numeric value of the next 4-digit chunk. |
| unsigned short temp1 = 0; |
| Int32 j = 0; |
| while ((j < 4) && (i+j < actualSourceLength)) { |
| temp1 = temp1*10 + actualSourceData[i+j]; |
| j++; |
| } |
| unsigned short power = powersOfTen[j - 1]; |
| |
| // Multiply the previous Big Num by 10^4 and add the value |
| // of the current chunk to it. It is more efficient to insert the |
| // multiplication and addition code here than to call the Helper() |
| // methods. |
| temp = ((ULng32) targetDataInShorts[0]) * power + temp1; |
| targetDataInShorts[0] = tempParts.remainder; |
| for (j = 1; j < finalTargetLengthInShorts; j++) { |
| temp = ((ULng32) targetDataInShorts[j]) * power + tempParts.carry; |
| targetDataInShorts[j] = tempParts.remainder; |
| } |
| if (tempParts.carry) { |
| if (finalTargetLengthInShorts >= targetLengthInShorts) |
| return -1; |
| finalTargetLengthInShorts++; |
| targetDataInShorts[finalTargetLengthInShorts - 1] = tempParts.carry; |
| } |
| } |
| |
| return 0; |
| |
| } |
| |
| // The following method converts a given Big Num (with sign) into |
| // its equivalent BCD string representation (with the more significant |
| // decimal digits in the lower addresses). |
| |
| short BigNumHelper::ConvBigNumWithSignToBcdHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData, |
| NAMemory * heap) |
| { |
| char sign = BIGN_GET_SIGN(sourceData, sourceLength); |
| |
| // Set up sign. |
| targetData[0] = (sign) ? '-' : '+'; |
| |
| // Temporarily clear sign |
| BIGN_CLR_SIGN(sourceData, sourceLength); |
| |
| short returnValue = BigNumHelper::ConvBigNumToBcdHelper(sourceLength, |
| targetLength - 1, |
| sourceData, |
| targetData + 1, |
| heap); |
| |
| // Restore sign |
| if (sign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| |
| return returnValue; |
| } |
| |
| // The following method converts a given BCD string representation |
| // (with sign, and with the more significant decimal digits in the lower |
| // addresses) into its equivalent Big Num representation. |
| |
| short BigNumHelper::ConvBcdToBigNumWithSignHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData) |
| { |
| short returnValue = BigNumHelper::ConvBcdToBigNumHelper(sourceLength - 1, |
| targetLength, |
| sourceData + 1, |
| targetData); |
| |
| // Set up sign after magnitude set. TargetData already cleared. |
| if (sourceData[0] == '-') |
| BIGN_SET_SIGN(targetData, targetLength); |
| |
| return returnValue; |
| } |
| |
| |
| // The following method converts a given Big Num (without sign) into |
| // its equivalent ASCII string representation (with the more significant |
| // decimal digits in the lower addresses). |
| |
| short BigNumHelper::ConvBigNumToAsciiHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData, |
| NAMemory * heap) |
| { |
| |
| // Convert to BCD representation (without sign). |
| short returnValue = BigNumHelper::ConvBigNumToBcdHelper(sourceLength, |
| targetLength, |
| sourceData, |
| targetData, |
| heap); |
| // Convert from BCD to ASCII. |
| for (Int32 i = 0; i < targetLength; i++) |
| targetData[i] += '0'; |
| |
| return returnValue; |
| |
| } |
| |
| // The following method converts a given ASCII string representation |
| // (without sign, and with the more significant decimal digits in the lower |
| // addresses) into its equivalent Big Num representation. |
| |
| short BigNumHelper::ConvAsciiToBigNumHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData) |
| { |
| // Temporarily convert source from ASCII to BCD. |
| Int32 i = 0; |
| for (i = 0; i < sourceLength; i++) |
| sourceData[i] -= '0'; |
| |
| short returnValue = BigNumHelper::ConvBcdToBigNumHelper(sourceLength, |
| targetLength, |
| sourceData, |
| targetData); |
| // Restore source to ASCII. |
| for (i = 0; i < sourceLength; i++) |
| sourceData[i] += '0'; |
| |
| return returnValue; |
| |
| } |
| |
| // The following method converts a given Big Num (with sign) into |
| // its equivalent ASCII string representation (with the more significant |
| // decimal digits in the lower addresses). |
| |
| short BigNumHelper::ConvBigNumWithSignToAsciiHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData, |
| NAMemory * heap) |
| { |
| char sign = BIGN_GET_SIGN(sourceData, sourceLength); |
| |
| // Set up sign. |
| targetData[0] = (sign) ? '-' : '+'; |
| |
| // Temporarily clear sign |
| BIGN_CLR_SIGN(sourceData, sourceLength); |
| |
| short returnValue = BigNumHelper::ConvBigNumToAsciiHelper(sourceLength, |
| targetLength - 1, |
| sourceData, |
| targetData + 1, |
| heap); |
| |
| // Restore sign |
| if (sign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| |
| return returnValue; |
| } |
| |
| // The following method converts a given ASCII string representation |
| // (with sign, and with the more significant decimal digits in the lower |
| // addresses) into its equivalent Big Num representation. |
| |
| short BigNumHelper::ConvAsciiToBigNumWithSignHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData) |
| { |
| short returnValue = BigNumHelper::ConvAsciiToBigNumHelper(sourceLength - 1, |
| targetLength, |
| sourceData + 1, |
| targetData); |
| |
| // Set up sign. |
| if (sourceData[0] == '-') |
| BIGN_SET_SIGN(targetData, targetLength); |
| |
| return returnValue; |
| } |
| |
| // Given a desired precision of a Big Num, the following method calculates |
| // the required storage length (including the sign). We assume that the |
| // precision is > 0. |
| |
| Lng32 BigNumHelper::ConvPrecisionToStorageLengthHelper(Lng32 precision) |
| { |
| // The storage length is always a multiple of 2 bytes, and at minimum, 8 bytes |
| // long. 1 bit must be available for the sign. Thus we use the formula: |
| // |
| // storage length = ceil((precision*log2(10) + 1)/16) |
| // |
| short err = 0; |
| |
| // Change precision to be a minimum of 18 (i.e. 8 bytes) |
| if (precision < 18) |
| precision = 18; |
| |
| Lng32 stLen = (2*(Lng32)(MathCeil((precision*0.208) + 0.062, err))); |
| |
| if (err) |
| return -1; // is -1 error return code from here??? |
| |
| return stLen; |
| } |
| |
| |
| // The following method converts an integer, 10^exponent, to a Big Num |
| // representation (without sign). The given exponent should be >= 0. The |
| // given targetData should have a length which is a multiple of 8. |
| |
| short BigNumHelper::ConvPowersOfTenToBigNumHelper(Lng32 exponent, |
| Lng32 targetLength, |
| Lng32 * finalTargetLength, |
| char * targetData) |
| |
| { |
| // If exponent is small enough, copy Big Num from precomputed table. |
| if (exponent < sizeof(powersOfTenInBigNumForm)/8) { |
| for (Int32 k = 0; k < 8 ; k++) |
| targetData[k] = ((char *) (powersOfTenInBigNumForm + exponent*4))[k]; |
| *finalTargetLength = 8; |
| return 0; |
| } |
| |
| // Otherwise, we have to actually compute 10^exponent iteratively. |
| // Recast from bytes to unsigned shorts. |
| unsigned short * targetDataInShorts = (unsigned short *) targetData; |
| *finalTargetLength = BigNumHelper::ConvPrecisionToStorageLengthHelper(exponent); |
| |
| Lng32 diffExponent = exponent - sizeof(powersOfTenInBigNumForm)/8 + 1; |
| |
| #ifdef NA_LITTLE_ENDIAN |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short remainder; |
| unsigned short carry; |
| } tempParts; |
| }; |
| #else |
| union { |
| ULng32 temp; |
| struct { |
| unsigned short carry; |
| unsigned short remainder; |
| } tempParts; |
| }; |
| #endif |
| |
| // Initialize the Big Num to 10^(sizeof(powersOfTenInBigNumForm)/8 - 1) |
| Int32 k = 0; |
| for (k = 0; k < 8; k++) |
| targetData[k] = ((char *) (powersOfTenInBigNumForm + sizeof(powersOfTenInBigNumForm)/2 - 4))[k]; |
| Lng32 currentTargetLengthInShorts = 4; |
| |
| // Multiply the Big Num repeatedly by 10^4 (excepting the last |
| // multiplication, which is by 10^(diffExponent%4). It is more |
| // efficient to insert the multiplication code here than to |
| // call the mulHelper() method. |
| |
| for (Int32 i = 0; i < diffExponent; i += 4) { |
| |
| unsigned short power; |
| if (i + 4 <= diffExponent) |
| power = 10000; |
| else |
| power = powersOfTen[(diffExponent % 4) - 1]; |
| |
| temp = ((ULng32) targetDataInShorts[0]) * power; |
| targetDataInShorts[0] = tempParts.remainder; |
| Int32 j = 1; |
| for (j = 1; j < currentTargetLengthInShorts; j++) { |
| temp = ((ULng32) targetDataInShorts[j]) * power + tempParts.carry; |
| targetDataInShorts[j] = tempParts.remainder; |
| } |
| if (tempParts.carry) { |
| currentTargetLengthInShorts++; |
| targetDataInShorts[currentTargetLengthInShorts - 1] = tempParts.carry; |
| } |
| |
| } |
| |
| // Fill up the trailing part of the target with zeros. |
| for (k = 2*currentTargetLengthInShorts; k < *finalTargetLength; k++) |
| targetData[k] = 0; |
| |
| return 0; |
| |
| } |
| |
| // The following converts an Int64 to a Big Num (with sign). |
| |
| short BigNumHelper::ConvInt64ToBigNumWithSignHelper(Int32 targetLength, |
| Int64 sourceData, |
| char * targetData, |
| NABoolean isUnsigned) |
| |
| { |
| Int32 tgtLength16 = targetLength >> 1; |
| UInt16* tgt = (UInt16*)targetData; |
| Int64* tgt64 = (Int64*)targetData; |
| NABoolean isNeg = FALSE; |
| |
| |
| // Initialize magnitude of target to zero. |
| for (Int32 k = 0; k < tgtLength16; k++) |
| tgt[k] = 0; |
| |
| if ((NOT isUnsigned) && (sourceData < 0)) { |
| sourceData = -sourceData; |
| isNeg = TRUE; |
| } |
| |
| *tgt64 = sourceData; |
| |
| // If little endian, do nothing, target is already in correct form. |
| #ifndef NA_LITTLE_ENDIAN |
| UInt16 temp1 = tgt[0]; |
| UInt16 temp2 = tgt[1]; |
| tgt[0] = tgt[3]; |
| tgt[1] = tgt[2]; |
| tgt[2] = temp2; |
| tgt[3] = temp1; |
| #endif |
| |
| if (isNeg) |
| BIGN_SET_SIGN(tgt, targetLength); |
| |
| return 0; |
| |
| } |
| |
| // The following converts a Big Num (with sign) into an Int64. |
| |
| short BigNumHelper::ConvBigNumWithSignToInt64Helper(Lng32 sourceLength, |
| char * sourceData, |
| void * targetDataPtr, |
| NABoolean isUnsigned) |
| |
| { |
| UInt64 *uTargetData = (UInt64*)targetDataPtr; |
| Int64 *targetData = (Int64*)targetDataPtr; |
| |
| // Recast from bytes to unsigned shorts. |
| unsigned short * sourceDataInShorts = (unsigned short *) sourceData; |
| Lng32 sourceLengthInShorts = sourceLength/2; |
| char srcSign = BIGN_GET_SIGN(sourceData, sourceLength); |
| |
| // Clear source sign temporarily |
| BIGN_CLR_SIGN(sourceData, sourceLength); |
| |
| // Remove trailing zeros in source. Note that we want a length of 4 unsigned shorts. |
| while (sourceDataInShorts[sourceLengthInShorts - 1] == 0 && sourceLengthInShorts > 4) |
| sourceLengthInShorts--; |
| |
| // Check for overflow. Source cannot have more than 4 unsigned shorts. |
| if (sourceLengthInShorts > 4) { |
| // Restore sign in source |
| if (srcSign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| return -1; |
| } |
| |
| // Copy the magnitude of source to target. |
| // TODO: unaligned store here |
| *targetData = *((Int64 *) sourceData); |
| |
| // Restore sign in source |
| if (srcSign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| |
| #ifdef NA_LITTLE_ENDIAN |
| // Do nothing, target already in correct format. |
| #else |
| // Reverse the shorts in the target. |
| unsigned short * targetDataInShorts = (unsigned short *) targetData; |
| |
| unsigned short temp = targetDataInShorts[0]; |
| targetDataInShorts[0] = targetDataInShorts[3]; |
| targetDataInShorts[3] = temp; |
| temp = targetDataInShorts[1]; |
| targetDataInShorts[1] = targetDataInShorts[2]; |
| targetDataInShorts[2] = temp; |
| #endif |
| |
| // We now check the sign of the source. Unfortunately there are complications. |
| // The target, an Int64, ranges between 2^63-1 and -2^63, which is asymmetric. |
| // We have to make sure that the source did not contain a Big Num outside this range. |
| |
| if (srcSign == 0) { // source is positive. |
| if (isUnsigned) |
| return 0; // all values are ok |
| |
| else if (*targetData >= 0) // target magnitude is between 0 and 2^63-1. |
| return 0; |
| else // target magnitude is beyond 2^63-1. |
| return -1; |
| } |
| else { // source is negative. |
| if (isUnsigned) |
| return -1; // error |
| else if (*targetData >= 0) { // target magnitude is between 0 and 2^63-1. |
| *targetData = -*targetData; |
| return 0; |
| } |
| else if (*targetData == LLONG_MIN) // target magnitude is 2^63. We do not even |
| // have to negate the target, because the bit |
| // representations of 2^63 and -2^63 (the latter |
| // in 2's-complement) are the same. |
| return 0; |
| else // target magnitude is beyond 2^63 |
| return -1; |
| } |
| |
| } |
| |
| |
| // The following converts a BIGNUM (with sign) into Int64 and scale it, |
| // returning information about the conversion to the caller (e.g. |
| // truncations, overflows). |
| // |
| // The return value can have 5 possible values: |
| // 0: the conversion was ok |
| // 1: the result was rounded up to LLONG_MIN |
| // 2: the result was rounded down to LLONG_MAX |
| // 3: the result was rounded up |
| // 4: the result was rounded down |
| |
| short BigNumHelper::ConvBigNumWithSignToInt64AndScaleHelper(Lng32 sourceLength, |
| char * sourceData, |
| Int64 * targetData, |
| Lng32 exponent, |
| NAMemory * heap) |
| { |
| |
| Lng32 sourceLengthInShorts = sourceLength/2; |
| unsigned short * targetDataInShorts = (unsigned short *) targetData; |
| |
| Lng32 absExponent = (exponent >= 0 ? exponent : -exponent); |
| |
| char srcSign = BIGN_GET_SIGN(sourceData, sourceLength); |
| |
| // Clear source sign temporarily |
| BIGN_CLR_SIGN(sourceData, sourceLength); |
| |
| // Allocate temp space for various calculations: |
| |
| // Allocate space for the scale factor, which is a Big Num (without sign) with value 10^(|exponent|). |
| Lng32 crudeScaleFactorLength = BigNumHelper::ConvPrecisionToStorageLengthHelper(absExponent + 1); |
| unsigned short * scaleFactorInShorts = new (heap) unsigned short [crudeScaleFactorLength/2]; |
| char * scaleFactor = (char *) scaleFactorInShorts; |
| |
| // Allocate space for temporary Big Num (without sign) to store source after scaling. |
| unsigned short * sourceDataAfterScalingInShorts = new (heap) unsigned short [(crudeScaleFactorLength + sourceLength)/2]; |
| char * sourceDataAfterScaling = (char *) sourceDataAfterScalingInShorts; |
| Lng32 sourceLengthAfterScalingInShorts; |
| |
| // Allocate temp space for the division routine; see DivHelper for details. |
| unsigned short * tempDataInShorts = new (heap) unsigned short [3 * (sourceLength) / 2 + 3]; |
| char * tempData = (char *) tempDataInShorts; |
| |
| Lng32 scaleFactorLength; |
| BigNumHelper::ConvPowersOfTenToBigNumHelper(absExponent, |
| crudeScaleFactorLength, |
| &scaleFactorLength, |
| scaleFactor); |
| |
| // Since the above function returns a Big Num with length a multiple of 8, there may be |
| // trailing zeros. Adjust the length to ignore trailing zeros. |
| Lng32 scaleFactorLengthInShorts = scaleFactorLength/2; |
| while (scaleFactorInShorts[scaleFactorLengthInShorts - 1] == 0 && scaleFactorLengthInShorts > 1) |
| scaleFactorLengthInShorts--; |
| scaleFactorLength = 2*scaleFactorLengthInShorts; |
| |
| short anyTruncation = 0; |
| |
| if (exponent < 0) { |
| // If exponent is negative, we need to scale up. Thus divide source by scaleFactor. |
| // If there is a remainder, this signifies that some truncation occurred. |
| |
| if (scaleFactorLengthInShorts > sourceLengthInShorts) { |
| // I.e. the scaleFactor is longer than the magnitude of the source, |
| // thus everything got truncated! Set source after scaling to zero. |
| for (Int32 k = 0; k < (crudeScaleFactorLength + sourceLength); k++) |
| sourceDataAfterScaling[k] = 0; |
| sourceLengthAfterScalingInShorts = 4; |
| anyTruncation = 1; |
| } |
| else if (scaleFactorLengthInShorts == 1) { |
| anyTruncation = BigNumHelper::SimpleDivHelper(sourceLength, |
| 2, |
| sourceData, |
| scaleFactor, |
| sourceDataAfterScaling); |
| sourceLengthAfterScalingInShorts = sourceLengthInShorts; |
| } |
| else { |
| anyTruncation = BigNumHelper::DivHelper(sourceLength, |
| scaleFactorLength, |
| sourceData, |
| scaleFactor, |
| sourceDataAfterScaling, |
| tempData); |
| sourceLengthAfterScalingInShorts = sourceLengthInShorts; |
| } |
| } |
| |
| else { |
| // If exponent is positive, we need to scale down, so multiply source by scaleFactor. |
| BigNumHelper::MulHelper(sourceLength + scaleFactorLength, |
| sourceLength, // ignore the sign byte |
| scaleFactorLength, |
| sourceData, |
| scaleFactor, |
| sourceDataAfterScaling); |
| sourceLengthAfterScalingInShorts = sourceLengthInShorts + scaleFactorLengthInShorts; |
| |
| } |
| |
| // Adjust the length of source after scaling to ignore trailing zeros (we do not have to |
| // go below a length of 4). |
| while (sourceDataAfterScalingInShorts[sourceLengthAfterScalingInShorts - 1] == 0 |
| && sourceLengthAfterScalingInShorts > 4) |
| sourceLengthAfterScalingInShorts--; |
| |
| |
| short retValue = 0; |
| |
| // Check for overflow. After scaling, the magnitude of source cannot have more |
| // than 4 unsigned shorts. |
| if (sourceLengthAfterScalingInShorts > 4) { |
| if (srcSign == 0) { // source is positive. |
| *targetData = LLONG_MAX; |
| retValue = 2; // the result was rounded down to LLONG_MAX. |
| } |
| else { |
| *targetData = LLONG_MIN; |
| retValue = 1; // the result was rounded up to LLONG_MIN. |
| } |
| } |
| |
| else { |
| |
| // Copy the magnitude of source to target. |
| *targetData = *((Int64 *) sourceDataAfterScaling); |
| |
| #ifdef NA_LITTLE_ENDIAN |
| // Do nothing, target already in correct format. |
| #else |
| // Reverse the shorts in the target. |
| unsigned short temp = targetDataInShorts[0]; |
| targetDataInShorts[0] = targetDataInShorts[3]; |
| targetDataInShorts[3] = temp; |
| temp = targetDataInShorts[1]; |
| targetDataInShorts[1] = targetDataInShorts[2]; |
| targetDataInShorts[2] = temp; |
| #endif |
| |
| // The target, an Int64, should range between 2^63-1 and -2^63, which is asymmetric. |
| // We have to make sure that the source did not contain a Big Num outside this range. |
| |
| if (srcSign == 0) { // source is positive. |
| |
| if (*targetData < 0) { // target magnitude is beyond 2^63-1. |
| *targetData = LLONG_MAX; |
| retValue = 2; // the result was rounded down to LLONG_MAX. |
| } |
| |
| } |
| else { // source is negative. |
| |
| if (*targetData < 0 && *targetData != LLONG_MIN) { // target magnitude is beyond 2^63 |
| *targetData = LLONG_MIN; |
| retValue = 1; // the result was rounded up to LLONG_MIN. |
| } |
| else if (*targetData != LLONG_MIN) { |
| // target magnitude is between 0 and 2^63. |
| // The value LLONG_MIN is already in correct format and doesn't |
| // need to be negated. |
| *targetData = -*targetData; |
| } |
| } |
| |
| if (retValue == 0 && anyTruncation) { |
| if (srcSign == 0) |
| retValue = 4; // the result was rounded down. |
| else |
| retValue = 3; // the result was rounded up; |
| } |
| |
| } |
| |
| NADELETEBASIC(scaleFactorInShorts, (heap)); |
| NADELETEBASIC(sourceDataAfterScalingInShorts, (heap)); |
| NADELETEBASIC(tempDataInShorts, (heap)); |
| |
| // Restore sign in source |
| if (srcSign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| |
| return retValue; |
| |
| } |
| |
| // The following converts a Big Num to a Big Num. |
| |
| short BigNumHelper::ConvBigNumWithSignToBigNumWithSignHelper(Lng32 sourceLength, |
| Lng32 targetLength, |
| char * sourceData, |
| char * targetData) |
| { |
| // Recast char strings as arrays of unsigned shorts |
| unsigned short * sourceDataInShorts = (unsigned short *) sourceData; |
| unsigned short * targetDataInShorts = (unsigned short *) targetData; |
| Lng32 sourceLengthInShorts = sourceLength/2; // length in number of shorts. |
| |
| char srcSign = BIGN_GET_SIGN(sourceData, sourceLength); |
| |
| // Clear sign bit |
| BIGN_CLR_SIGN(sourceData, sourceLength); |
| |
| // Ignore trailing zeros in source. Minimum number of shorts in source is 2. |
| while ((sourceDataInShorts[sourceLengthInShorts - 1] == 0) && (sourceLengthInShorts > 2)) |
| sourceLengthInShorts--; |
| |
| // Return error if overflow |
| if (sourceLengthInShorts > targetLength/2) { |
| // Reset sign bit of source |
| if (srcSign) |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| return -1; |
| } |
| |
| // Initialize magnitude of target to zeros. |
| Int32 k = 0; |
| for (k = 0; k < targetLength; k++) |
| targetData[k] = 0; |
| |
| // Copy source to target. |
| for (k = 0; k < sourceLengthInShorts; k++) |
| targetDataInShorts[k] = sourceDataInShorts[k]; |
| |
| // Restore sign in source and set sign in target |
| if (srcSign) { |
| BIGN_SET_SIGN(sourceData, sourceLength); |
| BIGN_SET_SIGN(targetData, targetLength); |
| } |
| |
| return 0; |
| } |
| |
| |
| |
