Adding XOR function to bigint library

Question

I'm using this Big Integer library for Javascript: http://www.leemon.com/crypto/BigInt.js and I need to be able to XOR two bigInts together and sadly the library doesn't include such a function. The library is relatively simple so I don't think it's a huge task, just confusing.

I've been trying to hack one together but not having much luck, would be very grateful if someone could lend me a hand. This is what I've attempted (might be wrong). But im guessing the structure is going to be quite similar to some of the other functions in there.

function xor(x, y)
{
    var c, k, i;
    var result = new Array(0); // big int for result

    k=x.length>y.length ? x.length : y.length; // array length of the larger num

    // Make sure result is the correct array size? maybe:
    result = expand(result, k); // ?

    for (c=0, i=0; i < k; i++)
    {
        // Do some xor here
    }

    // return the bigint xor result
    return result;
}

What confuses me is I don't really understand how it stores numbers in the array blocks for the bigInt. I don't think it's a case of simply bigintC[i] = bigintA[i] ^ bigintB[i], then most other functions have some masking operation at the end that I don't understand. I would really appreciate any help getting this working.

Thanks

score 1 · Accepted Answer · answered Jun 09 '10 at 17:05

It looks like that js is storing an int into bpe bits per array element.

Look at this:

//convert the integer t into a bigInt with at least the given number of bits.
//the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word)
//Pad the array with leading zeros so that it has at least minSize elements.
//There will always be at least one leading 0 element.
function int2bigInt(t,bits,minSize) {   
  var i,k;
  k=Math.ceil(bits/bpe)+1;
  k=minSize>k ? minSize : k;
  buff=new Array(k);
  copyInt_(buff,t);
  return buff;
}

and the comment at the top of the file:

// This code defines a bigInt library for arbitrary-precision integers.
// A bigInt is an array of integers storing the value in chunks of bpe bits, 
// little endian (buff[0] is the least significant word).

So walking the array, doing a bitwise XOR of bpe bits of each array element should work.

You might have to take care if one if the bigints is a negative number, though, as the representation there is 2s-complement.

Thanks a lot @Moron, this appears to work successfully with some added length checks / 0 padding. I haven't tested negative integers as I wont be using them. But it's working fine for 128-bit+ integers :) — Jason Gooner, Jun 09 '10 at 18:20

Sean Kinsey · Answer 2 · 2010-06-09T17:29:31.307

-2

Javascript has built-in support for bitwise operators https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Operators/Bitwise_Operators

alert(14 ^ 9) // 7

UPDATE
Should have read the question better, the OP is obviously already aware of the operators

edited Jun 09 '10 at 17:29

answered Jun 09 '10 at 16:35

Sean Kinsey

37,689
7
52
71

I cant just apply that to two big integers though can I, given their special array storage format. – Jason Gooner Jun 09 '10 at 16:39
Bitwise operations and large javascript integers do not mix very well (mostly because they're not really integers) - http://stackoverflow.com/questions/2983206/bitwise-and-in-javascript-with-a-64-bit-integer/2983294#2983294 – Andy E Jun 09 '10 at 16:41
The alternative is I output x and y to binary strings, and iterate through doing a comparison between the 1s and 0s, but I fear this would be seriously inefficient. – Jason Gooner Jun 09 '10 at 16:44
@Jason - No, but wasn't the point to put something where you said `// Do some xor here` ? – Sean Kinsey Jun 09 '10 at 17:27

Adding XOR function to bigint library

2 Answers2