«

Hi,

I'm trying to implement a simple hash algorith called rs_hash in
javascript,
but I cannot get a correct result.

In c the code looks like this:



signed char myArray[6];

myArray[0]= 0x01;
myArray[1]= 0x02;
myArray[2]= 0x03;
myArray[3]= 0x04;
myArray[4]= 0x05;
myArray[5]= 0x06;

signed int b = 378551;
signed int a = 63689;
signed int hash = 0;
int i= 0;
int len= 6;

for( i= 0; i<len; i++ )
{
hash = hash * a + myArray[i];
a = a * b;
}

return hash;


and my try in javascripts looks like this


var myArray = new Array();

myArray[0] = 0x01;
myArray[1] = 0x02;
myArray[2] = 0x03;
myArray[3] = 0x04;
myArray[4] = 0x05;
myArray[5] = 0x06;

var b = 378551;
var a = 63689;
var hash = 0;
var i = 0;
var len= 6;

for( i== 0; i<len; i++)
{
hash = hash * a + myArray[i];
a = a * b;
}

return hash;




The c functions returns -1596271655 (2698695641 when casted to
unsigned)
while the the javacsript funtion returns 4.922527108004972e+107

I guess this has to do with the fact that javascript has typeless
variables, but is there a way to
cast them to signed integers?

I tried casting some variables
var b = parseInt('378551');
var a = parseInt('63689');
var hash = parseInt('0');

but this didn't help. My some out there can?

wrote on 07 feb 2007 in comp.lang.javascript:

>
> for( i== 0; i<len; i++)
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
> The c functions returns -1596271655 (2698695641 when casted to
> unsigned)
> while the the javacsript funtion returns 4.922527108004972e+107
>
> I guess this has to do with the fact that javascript has typeless
> variables, but is there a way to
> cast them to signed integers?
>
> I tried casting some variables
> var b = parseInt('378551');
> var a = parseInt('63689');
> var hash = parseInt('0');
>
> but this didn't help. My some out there can?
>

var b = parseInt('378551');
or
var b = 378551;
That would not help, as it does not change the type of the variable:


The best you can do is do a Math.floor after every computation,
to keep the results as an integer.
[This is what you should do in C too, methinks, but possibly it is a
default behavour of storing a noninteger float in an integer variable
there.]

for( i== 0; i<len; i++) {
hash = Math.floor(hash * a) + myArray[i];
a = a * b;
}

However possibly
a = a * b;
could loose presision?


--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

Javascript is reporting the correct result. The C code is producing an
error result. You have a signed int hash which, unless you're working
in a 64 bit environment, is capped at 2 billion. Your code exceeds 2
billion and goes negative which is why C returns a negative number.

Javascript isn't rolling over, it's reporting the actual value of the
algorithm which really is an obscenely long number 107 places to be
more acurate which means the C code is not only rolling over once it is
rolling over MULTIPLE times like a car's odometer if you were to drive
from here to the nearest start -- billions and billions of miles but the
odometer would report some number between 0 and 999,999 miles.

So the question isn't if javascript can do complex calculation, it's can
C do it Well yea it can, but not with a signed int in this case



wrote:
> Hi,
>
> I'm trying to implement a simple hash algorith called rs_hash in
> javascript,
> but I cannot get a correct result.
>
> In c the code looks like this:
>
>
>
> signed char myArray[6];
>
> myArray[0]= 0x01;
> myArray[1]= 0x02;
> myArray[2]= 0x03;
> myArray[3]= 0x04;
> myArray[4]= 0x05;
> myArray[5]= 0x06;
>
> signed int b = 378551;
> signed int a = 63689;
> signed int hash = 0;
> int i= 0;
> int len= 6;
>
> for( i= 0; i<len; i++ )
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
>
> and my try in javascripts looks like this
>
>
> var myArray = new Array();
>
> myArray[0] = 0x01;
> myArray[1] = 0x02;
> myArray[2] = 0x03;
> myArray[3] = 0x04;
> myArray[4] = 0x05;
> myArray[5] = 0x06;
>
> var b = 378551;
> var a = 63689;
> var hash = 0;
> var i = 0;
> var len= 6;
>
> for( i== 0; i<len; i++)
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
>
>
>
> The c functions returns -1596271655 (2698695641 when casted to
> unsigned)
> while the the javacsript funtion returns 4.922527108004972e+107
>
> I guess this has to do with the fact that javascript has typeless
> variables, but is there a way to
> cast them to signed integers?
>
> I tried casting some variables
> var b = parseInt('378551');
> var a = parseInt('63689');
> var hash = parseInt('0');
>
> but this didn't help. My some out there can?
>


--
http://www.hunlock.com -- Musings in Javascript, CSS.
$FA

In comp.lang.javascript message <Xns98D0B5E417B0eejj99@194.109.133.242>,
Wed, 7 Feb 2007 16:52:49, Evertjan. <>
posted:
>
>
>The best you can do is do a Math.floor after every computation,
>to keep the results as an integer.

If the intermediate may be non-integer, is it necessarily too big?
Math.round might be safer.

If the work can be done with 32-bit variables, |0 might be considered.

Quantities of more than 32 bits can be represented as multiple 32-bit
variables.

--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links;
Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc.
L3 is not as far out as some have said.

On Feb 7, 7:40 pm, beach...@gmail.com wrote:
> Hi,
>
> I'm trying to implement a simple hash algorith called rs_hash in
> javascript,
> but I cannot get a correct result.
>
> In c the code looks like this:
>
> signed char myArray[6];
>
> myArray[0]= 0x01;
> myArray[1]= 0x02;
> myArray[2]= 0x03;
> myArray[3]= 0x04;
> myArray[4]= 0x05;
> myArray[5]= 0x06;
>
> signed int b = 378551;
> signed int a = 63689;
> signed int hash = 0;
> int i= 0;
> int len= 6;
>
> for( i= 0; i<len; i++ )
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
> and my try in javascripts looks like this
>
> var myArray = new Array();
>
> myArray[0] = 0x01;
> myArray[1] = 0x02;
> myArray[2] = 0x03;
> myArray[3] = 0x04;
> myArray[4] = 0x05;
> myArray[5] = 0x06;
>
> var b = 378551;
> var a = 63689;
> var hash = 0;
> var i = 0;
> var len= 6;
>
> for( i== 0; i<len; i++)
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
> The c functions returns -1596271655 (2698695641 when casted to
> unsigned)
> while the the javacsript funtion returns 4.922527108004972e+107
>
> I guess this has to do with the fact that javascript has typeless
> variables, but is there a way to
> cast them to signed integers?

As it was pointed out, the problem is with your C code, not with
JavaScript.
signed int holds values from -2,147,483,648 to 2,147,483,647 and your
calculations are going way beyond this border. It is called "type
overflow" and the exact error correction is not defined in C language
specifications. It means that depending on particular C/C++ compiler
you may get different results. As I can tell on your current C
compiler type overflow is resolved by simply truncating extra bits, so
from some point your hash = hash * a starts acting as some very fancy/
weird bitwise shift statement. If you are getting the needed results
with it then it is a very lucky coincidence.

In JavaScript all numbers are - at least officially - IEEE-754
floating point double precision, so even after 2,147,483,647 your hash
just keeps growing.

P.S. After you bring your C code into correct form and start porting
in JavaScript, keep in mind some important limits for big integers
summarized in Nielsen's table
<http://groups.google.com/group/comp....avascript/msg/
3833df1762d81fee>

On Feb 7, 4:40 pm, beach...@gmail.com wrote:
> I'm trying to implement a simple hash algorith called rs_hash in
> javascript, but I cannot get a correct result.
>
> In c the code looks like this:
>
> signed char myArray[6];
>
> myArray[0]= 0x01;
> myArray[1]= 0x02;
> myArray[2]= 0x03;
> myArray[3]= 0x04;
> myArray[4]= 0x05;
> myArray[5]= 0x06;
>
> signed int b = 378551;
> signed int a = 63689;
> signed int hash = 0;
> int i= 0;
> int len= 6;
>
> for( i= 0; i<len; i++ )
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
> and my try in javascripts looks like this
>
> var myArray = new Array();
>
> myArray[0] = 0x01;
> myArray[1] = 0x02;
> myArray[2] = 0x03;
> myArray[3] = 0x04;
> myArray[4] = 0x05;
> myArray[5] = 0x06;
>
> var b = 378551;
> var a = 63689;
> var hash = 0;
> var i = 0;
> var len= 6;
>
> for( i== 0; i<len; i++)
> {
> hash = hash * a + myArray[i];
> a = a * b;
> }
>
> return hash;
>
> The c functions returns -1596271655 (2698695641 when casted to
> unsigned)
> while the the javacsript funtion returns 4.922527108004972e+107
>
> I guess this has to do with the fact that javascript has typeless
> variables, but is there a way to cast them to signed integers?
<snip>

Having type less variable is irrelevant. Your problem is that
javascript uses an IEEE double precision floating point number as its
only numeric type. As a result you cannot "cast" a number to a
different numeric type (there are not other numeric types to "cast" it
to).

On the other hand, the double precision floating point number can
represent all values that can be represented in signed 32 bit integers
with precision.

> I tried casting some variables
> var b = parseInt('378551');
> var a = parseInt('63689');
> var hash = parseInt('0');
>
> but this didn't help. My some out there can?

It seems that what you want is to be able to multiply two numeric
values that can be represented as 32 bit signed integers and get the
same result as you would in C; another 32bit signed integer, but
probably the value that would be the lower 4 bytes of the 64 bit
integer that is the result of the multiplication of two 32 bit
integers.

I am reminded of assembly language programming a decade ago where the
CPU in use could do direct multiplication of 16 bit integers to
produce 32 bit results (as a limitation imposed by its registers being
32 bits wide). When you needed to multiply two 32 bit value you would
split them up into 4 16 bit value, do 4 multiplications and then shift
and add the results to get the desired 64 bit result spread across two
registers.

Internally javascript uses signed and unsigned 32 bit value with its
bitwise operations, and it is certainly possible to convert an
arbitrary floating point number into a value that can be represented
as a signed or unsigned 32 bit integer by applying a bit-wise
operation. Given this, and starting with values that can be
represented as signed 32 bit integers, it would be possible to create
a function that took two such values as input, split them up into
their upper and lower 16 bits and then performed the multiplication on
the parts (which must produce a results that can itself be represented
as 32 bit integers), shift and add those results and apply other
appropriate bitwise operations to produce a return value that was in
the range of signed 32 bit integers.

A quick attempt came up with:-

function test(){
var myArray =[
0x01,
0x02,
0x03,
0x04,
0x05,
0x06
];

var b = 378551;
var a = 63689;
var hash = 0;
var i = 0;
var len= 6;

for(i== 0;i<len;++i){
hash = (mul32(hash, a) + myArray[i]);
a = mul32(a, b);
}
return hash;
}

function mul32(a, b){
var aL = (a & 0xFFFF);
var bL = (b & 0xFFFF);
var aH = (a >>> 16);
var bH = (b >>> 16);
return ((((aH * bL) + (bH * aL))<<16) + ((aL * bL)|0))| 0;
}

Which does result in your -1596271655 value when executed, though I
have not tested it in comparison with how C would do multiplication of
32 bit signed integers to give a 32bit signed result.

Richard.

On Feb 8, 4:53 pm, "Richard Cornford" <Rich...@litotes.demon.co.uk>
wrote:
> It seems that what you want is to be able to multiply two numeric
> values that can be represented as 32 bit signed integers and get the
> same result as you would in C; another 32bit signed integer, but
> probably the value that would be the lower 4 bytes of the 64 bit
> integer that is the result of the multiplication of two 32 bit
> integers.

Actually the OP's question knocked me down a bit... By the style the
question was asked I felt that the C code snippet was something
obvious and meaningful to poster - while it was looking clearly wrong
from any common programming considerations. So I checked it out and I
be damned: there is someone Robert Sedgewick who is a rather famous
programming specialist AFAICT. Among other things he proposed a hash
key calculation algorithm commonly referred as RSHash or rs_hash
algorithm (by the first letters in the name). A pure C-form would be:

unsigned int RSHash(const std::string& str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = hash * a + str[i];
a = a * b;
}

return (hash & 0x7FFFFFFF);
}

I be damned once again: the entire algorithm is based on intentional
type overflow and engine error correction mechanics. What is going on
in this world?

VK said:

>I be damned once again: the entire algorithm is based on intentional
>type overflow and engine error correction mechanics. What is going on
>in this world?

C programmers (used to) do that all the time.
You know without doubt how big "unsigned int" is and that
there isn't any engine to try to correct anything.


--

In article < .com>, VK
<> writes

<snip>
>I be damned once again: the entire algorithm is based on intentional
>type overflow and engine error correction mechanics. What is going on
>in this world?

I'd have thought it's obvious what's going on. The whole point of a hash
operation is to turn a long string of various lengths into a short
result with a fixed length. A 32 bit result is a popular value, though
cryptographic hashes tend to be longer, say 20 bytes.

The OP's algorithm relies on anything over the size of an int (e.g 32
bits) being thrown away, so each step needs to finish with a modulo
operation. Unfortunately, the algorithm does hash * a where both hash
and a can be size-of-int long. (hash * a) will lose bits sometimes in
javascript since the integral part of a javascript number is only 56
bits long. As Richard said, the multiplication would have to be split
into parts; two would be sufficient when "ints" are 32 bits long.

John
--
John Harris

In comp.lang.javascript message <
oglegroups.com>, Thu, 8 Feb 2007 05:53:59, Richard Cornford
<> posted:
>
>Having type less variable is irrelevant. Your problem is that
>javascript uses an IEEE double precision floating point number as its
>only numeric type. As a result you cannot "cast" a number to a
>different numeric type (there are not other numeric types to "cast" it
>to).
>


The tail of that is not really true, except on a strict interpretation
of "cast".

Javascript currently only has one built-in numeric type; but one can use
an array of digits to represent, exactly, numbers with greater
resolution than an IEEE Double can deal with. The standard operators
cannot be used directly, but one can write a function Plus with two
array arguments returning an array representing the sum, etc. etc.

ASIDE : In fact, I've done more or less that in Pascal/Delphi in
LONGCALC (via sig line 3) - it will do integer arithmetic on signed
numbers of up to 65520 digits (99999999 in Delphi) to any base in 2..16,
including swapping bases in mid-stream. Feel free to translate it (with
appropriate attribution) into Javascript; IIRC, it's only about 3000
lines, some blank. Command line "longcalc 99 fac #ge wrt wrt" gives
"+4 +9" showing that Gregorian Easter Sunday of the year 99-factorial
will be April 9th[*].


I've also done a part of that in the code that converts an IEEE Double's
sign+mantissa to an exact decimal string - functions Add() & Halve()
used in <URL:http://www.merlyn.demon.co.uk/js-misc0.htm#DW4> - perhaps
you remember an article saying (not necessarily in those words) that
Number("1.035") = 1.034999999999999920063942226988729089498519897460 9375
?


All arithmetic can be done with array-of-Boolean being the only numeric
type.


[*] It should be on the same date for all factorial years from 19! up.
Actually, it's the same in AD 18! and AD 16! and AD 11! which I suspect
of being coincidences.

--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk DOS 3.3, 6.20; WinXP.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
PAS EXE TXT ZIP via <URL:http://www.merlyn.demon.co.uk/programs/00index.htm>
My DOS <URL:http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.