bitwise shifting in reverse in javascript

Question

I am wondering how I can make the following bit shifting process in reverse?

chr1 = (enc1 | ((enc2 & 3) << 6));
chr2 = (enc2 >> 2) | ((enc3 & 0x0F) << 4);
chr3 = (enc3 >> 4) | (enc4 << 2);

This is basically shifting the bits for a decoding script Im using. Im wondering is there a way to reverse this process, for encoding instead of decoding?

This comes from the following script which decodes in base64:

Base64 = {
        _keyStr: ".ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+=",
        decode: function( input ) {
                    var output = "";
                    var hex = "";
                    var chr1, chr2, chr3 = "";
                    var enc1, enc2, enc3, enc4 = "";
                    var i = 0;
                    var base64test = /[^A-Za-z0-9\+\.\=]/g;

                    do {
                        enc1 = this._keyStr.indexOf(input.charAt(i++)) ;
                        enc2 = this._keyStr.indexOf(input.charAt(i++)) ;
                        enc3 = this._keyStr.indexOf(input.charAt(i++)) ;
                        enc4 = this._keyStr.indexOf(input.charAt(i++)) ;

                        chr1 = (enc1 | ((enc2 & 3) << 6));                                                                                                             
                        chr2 = (enc2 >> 2) | ((enc3 & 0x0F) << 4);                                                                                                     
                        chr3 = (enc3 >> 4) | (enc4 << 2);


                        output = output + String.fromCharCode(chr1);
                        if (enc3 != 64) {
                            output = output + String.fromCharCode(chr2);
                        }
                        if (enc4 != 64) {
                            output = output + String.fromCharCode(chr3);
                        }
                        chr1 = chr2 = chr3 = "";
                        enc1 = enc2 = enc3 = enc4 = "";
                    } while (i < input.length);

                    return (output);
                }
}

looks to me like there is information loss in moving from enc1234 to chr123... if so it can't be reversed. — Christian Cerri
– Christian Cerri, Commented May 5, 2016 at 6:29

phihag · Accepted Answer · 2016-05-05 14:44:12Z

5

Observe the following calculations:

// enc = [0, 1, 0, 0]
chr1 = (0 | ((1 & 3) << 6)) = 64
chr2 = (1 >> 2) | ((0 & 0x0F) << 4) = 0
chr3 = (0 >> 4) | (0 << 2) = 0

// enc = [64, 0, 0, 0]
chr1 = (64 | ((0 & 3) << 6)) = 64
chr2 = (0 >> 2) | ((0 & 0x0F) << 4) = 0
chr3 = (0 >> 4) | (0 << 2) = 0

Since two inputs map to the same outputs, the function is not injective, i.e. cannot be reversed.

If you assume that all values of enc are <64, you can reverse it though:

enc1 = chr1 & 0x3f;
enc2 = (chr1 >> 6) | ((chr2 & 0xf) << 2);
enc3 = (chr2 >> 4) | ((chr3 & 0x3) << 4);
enc4 = chr3 >> 2;

Since the space of values isn't that large, you can simply test them all out, right here in your browser:

'use strict';

function _indicate(status) {
  var indicator = document.querySelector('.indicator');
  while (indicator.firstChild) {
    indicator.removeNode(firstChild);
  }
  indicator.setAttribute('class', status);
  indicator.appendChild(document.createTextNode(status));
}

function test(enc1, enc2, enc3, enc4) {
  var chr1 = (enc1 | ((enc2 & 3) << 6));
  var chr2 = (enc2 >> 2) | ((enc3 & 0x0F) << 4);
  var chr3 = (enc3 >> 4) | (enc4 << 2);

  var dec1 = chr1 & 0x3f;
  var dec2 = (chr1 >> 6) | ((chr2 & 0xf) << 2);
  var dec3 = (chr2 >> 4) | ((chr3 & 0x3) << 4);
  var dec4 = chr3 >> 2;

  if ((enc1 !== dec1) || (enc2 !== dec2) || (enc3 !== dec3) || (enc4 !== dec4)) {
    console.log('FAIL');
    console.log('chr ' + chr1 + ', ' + chr2 + ', ' + chr3);
    console.log('Expected/got: ' + enc1 + '/' + dec1 + ', ' + enc2 + '/' + dec2 + ', ' + enc3 + '/' + dec3 + ', ' + enc4 + '/' + dec4);
    _indicate('fail');
    throw new Error('Failed test');
  }
}


for (var enc1 = 0; enc1 < 63; enc1++) {
  for (var enc2 = 0; enc2 < 63; enc2++) {
    for (var enc3 = 0; enc3 < 63; enc3++) {
      for (var enc4 = 0; enc4 < 63; enc4++) {
        test(enc1, enc2, enc3, enc4);
      }
    }
  }
}
_indicate('pass');

.fail {
  background: red;
}
.pass {
  background: green;
}

<div class="indicator"></div>

edited May 5, 2016 at 14:44

answered May 5, 2016 at 6:31

phihag

289k75 gold badges475 silver badges489 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Ke. Over a year ago

Hi phihag, I've added the rest of the script to my question. Is it really not possible to create an encoding function, using the same bitwise shifting? It's just that I have seen many functions like this in the past and they always have a reverse (encoding) function, so my guess is that it is possible for this script. In this case, I don't have it and am trying to recreate on my own.

phihag Over a year ago

No, the above is a mathematical proof that it is not possible to write an encoding function if the encoding operates on arbitrary integers. However, you're in luck - your encoding just maps from [0, 64[ to [0, 255[, and therefore is reversible. I have added code that does that.

Aiman Al-Eryani Over a year ago

enc1 = chr1 && 0x3f; is that the logical and? Does this mean enc1 can only be 1 or 0?

Ke. Over a year ago

Hi phihag, thanks very much, however I cant seem to test whether it works. I've created another question about this where Ive given a test example. It's very close, but there is some bit shifting problem. stackoverflow.com/questions/37048873/…

phihag Over a year ago

@Ke. I added code to a test that proves the transformation to be correct. I apologize for the error in a previous version - the bitmask for enc1 should be 0xf.

|

Collectives™ on Stack Overflow

bitwise shifting in reverse in javascript

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related