Bit by a Hex String

[abitkin]

So here's the problem:
I have a hex string that is 104 bits. I need to shift the string 1 bit to the left (thus it will be 105 bits) add 1, and convert the result back into hex. Here's the code I have so far (and yes I know, I should have used strict and warnings):

sub shift_bs{
    %cs0=(
        '0' => '0',
        '1' => '2',
        '2' => '4',
        '3' => '6',
        '4' => '8',
        '5' => 'A',
        '6' => 'C',
        '7' => 'E',
        '8' => '0',
        '9' => '2',
        'a' => '4',
        'b' => '6',
        'c' => '8',
        'd' => 'A',
        'e' => 'C',
        'f' => 'E'
    );
    %cs1=(
        '0' => '1',
        '1' => '3',
        '2' => '5',
        '3' => '7',
        '4' => '9',
        '5' => 'B',
        '6' => 'D',
        '7' => 'F',
        '8' => '1',
        '9' => '3',
        'a' => '5',
        'b' => '7',
        'c' => '9',
        'd' => 'B',
        'e' => 'D',
        'f' => 'F'
    );
    $c1 = shift;
    $char_stream = shift;
    if($char_stream =~ /^$/){
        return $c1;
    }
    $char_stream =~ /^(.*)(.)$/;
    ($char_st,$char)=($1,$2);
    $c_ = int(hex($char)/8);
    $char2=($c1==1?$cs1{$char}:$cs0{$char});
    return ((shift_bs($c_,$char_st)).$char2);
}

The call to this sub is:

push @src, shift_bs(1,$source);

Where $source is the hex string that I'm trying to convert.

The problem is, I get nothing back. Any help would be apprecated. Oh, and for those wondering why I'm not using Math::BigInt, this script will be distributed, and it is likely that atleast one machine won't have that on it. (And as always, it is just as likely we'll discover that the machine is lacking this module when it is too late to fix it.)
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.

[Abigail-II]

I have a hex string that is 104 bits.

Huh? What exactly do you have? A bit string, or a string using hexadecimal numbers?

Oh, and for those wondering why I'm not using Math::BigInt, this script will be distributed, and it is likely that atleast one machine won't have that on it

Considering that Math::BigInt has been part of the standard distribution for a while, that seems unlikely. Furthermore, Math::BigInt lives on CPAN, so you should be able to distribute it with your program if you want to.

Abigail

[abitkin]

I have a hex string. Each charcter in a hex string represents 4 bits, thus my string length is 26 charcters. The number of bits was just to show that it could not be stored in a regular perl scalar.

As for Math::BigInt being in the default install, honestly I didn't know that. I've never been able to find a list of what's included by default and from which version on.

If I were to use Math::BigInt, how would I load the value in, as the documentation of the module does not describe loading hexidecimal values, just decimal values.

Finally, as to the point of Math::BigInt living on Cpan, well that only works if you have access to the internet.

This script is being put on number of machines that will be used in demo at a tradeshow, as a tool to use, in case of a problem with the application we are demoing. As such, I am not able to install it myself, but I'm sending the file to someone else, in marketing.

For that reason I must make it as simple as possible, as people in marketing are not what I'd consider "power users." Since I will not be able to see the machines till they are at the tradeshow, and we will not have internet at the tradeshow, this makes cpan preaty much useless.
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.

[Abigail-II]

Here's a Math::BigInt solution.

#!/usr/bin/perl

use strict;
use warnings;

use Math::BigInt;

$_ = "DEADBEEFBABEFACE1234567890";

my $num = Math::BigInt -> new (0);

# Convert the number to a Math::Int decimal number.
while (length) {
    my $chunk = substr $_, 0, 4, "";
    $num *= 2 ** (4 * length $chunk);
    $num  += hex $chunk;
}

# Multiply by 2, add 1.
$num *= 2;
$num += 1;

# Convert the Math::BigInt number to hex.
my @a;
while ($num) {
    push @a => sprintf "%X" => $num % 16;
    $num /= 16;
}
my $new = join "" => @a;

print $new, "\n";

And here's an Inline::BC solution:

#!/usr/bin/perl

use strict;
use warnings;

use Inline 'BC';

print x("DEADBEEFBABEFACE1234567890");

__DATA__
__BC__
ibase = 16
obase = 10
define x (a) {
    return (a * 2 + 1)
}

Abigail

[wirrwarr]

please use strict; if possible.
all the variables you use are global variables, so they are overwritten by the recursive call.
the solution is to my all variables.
when you want to double the value of your bitstring, you should call it with shift_bs(0,$source);.

daniel.

[abitkin]

Well that'll learn me. The one time I didn't use strict. Nice catch.
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.

[sgifford]

Here's a short program that does this with byte-at-a-time arithmetic. You can make it do word-at-a-time with a little playing, which should be faster.

#!/usr/bin/perl -w

use strict;

use constant WORDBYTES => 1;
use constant WORDBITS => WORDBYTES*8;
use constant WORDNYBBLES => WORDBYTES*2;
use constant WORDMASK => (2**WORDBITS)-1;

sub left_shift_hex_string
{
  my($bits,$str,$add)=@_;
  my $val = hex(substr($str,0,WORDNYBBLES));
  my $carryout = $val >> (2**WORDBYTES-$bits);

  if (length($str) > WORDNYBBLES)
  {
    my($carryin,$res)=left_shift_hex_string($bits,substr($str,WORDNYBB
+LES),$add);
    return ($carryout,sprintf "%x%s", ($val<<$bits | $carryin) & WORDM
+ASK, $res);
  }
  else
  {
    warn "val=$val, bits=$bits, add=$add\n";
    return($carryout,sprintf "%x", ($val<<$bits|$add)&WORDMASK);
  }
}


my($co,$val)=left_shift_hex_string(1,"00ffffff",0);

print "val=$val\n";

[Theo]

Shifting one bit to the left is the same as multilpying by 2. Can you just multiply the number by two and add one? Wouldn't that be a lot easier?

-ted-

[abitkin]

While I give you props for the simplicity of this solution, it is rather useless in this case. Once again it's the 64 bit integer limit of Perl that would keep me from doing this. (Actually 63, because of the sign, but anyways) My number is quite a bit larger than the standard Perl scalar. (no pun intended.)
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.

[TomDLux]

So this is a string of 26 characters, '0', '1', '2', '3', '4', '5', '6', , '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'; in other words ASCII values 48, 449, 50, 51, ,52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102. Isn't that somewhat inefficient, to use 8-bit characters to store hex values?

You could use BigInt; You could use a set of scalars to store N/billion & N%billion ....; You could use pack & unpack to store hex digits in 4 bits.

--
TTTATCGGTCGTTATATAGATGTTTGCA

[abitkin]

When you get to the hair edge of creating your own packets to use in simulation of network traffic, using chars to store words is actually standard practice, as it is better than storing the actually binary strings and most shifts (all those %4==0) are easy enough. I just had an odd shift number.

Your absolutly correct with pack and unpack, but I'll be honest with you, I hate pack and unpack. I have to play with them for way too long usally to get them to do what I want.
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.

[tcf22]

You can use << to do a bit shift to the left.

Also you should write if($char_stream =~ /^$/) as if(length($char_stream) == 0). No need to use a regex for that.

[abitkin]

As far as I can tell, using your bit shift assumes two things that I don't have.

The first is that my string is a decimal number. It isn't. I don't know what would happen if you shifted a string filled with hex by 1.

The second is, that my hex string would fit inside a scalar. Perl numbers are limited to 64 bits, and as I mentioned, this string is 104 bits. (When converted from hex to a binary stream.)

As for the length thing, yes, that is another way to do it, I was just going for simple at the time, and I didn't want to lookup length.
==
Kwyjibo. A big, dumb, balding North American ape. With no chin.