CRC (JavaScript)

RobotGymnast · #1 (**permalink**) 04-20-2008, 05:09 PM

Hi. I've been trying to make a CRC calculator (don't ask why I didn't just use somebody else's source code, I need to make it for certain specs), and I decided that in JavaScript I don't have to deal with casting issues and other stupid stuff that takes forever to fix, so I'd make a prototype in JavaScript just to make sure my code worked. It seems like it works, when I manually calculate, it returns the same result, but now if I run a CRC32 calculator, it returns different results than when I run it through my JavaScript one. So apparently I'm missing a step or something (or I can't find the right poly.. there's a few CRC32 polys). My math consists of the long division method when I'm doing it manually, so like:

Code:

poly ) input+augmentation
11100 ) letter g + 4 0s (because the poly is 5 digits, including implicit bit)
11100 ) 011001110000
           ^
           00000
           =
            11001
            ^
            11100
            =
             01011
             ^
             00000
             =
              10111
              ^
              11100
              =
               10110
               ^
               11100
               =
                10100
                ^
                11100
                =
                 10000
                 ^
                 11100
                 =
                  11000
                  ^
                  11100
                  =
                   0100 <-- Remainder of 4, the checksum

Basically I take w+1 digits (which is the amount of digits in the poly, including the implicit bit) from the message. If it starts with 1, XOR the thing with the poly, otherwise, XOR it with 0. Now take the last four digits of what you have left (AKA take off the first digit because it's always 0), and bring down another digit from the original message. Now XOR again if the thing starts with 1, etc. etc., until you've brought down the last digit and XORed for the last time.

The JavaScript uses a binary push method. It checks the first bit of the remaining binary string I have, if it's 1, it XORes, if it's 0, it doesn't, etc. Then it takes off that digit. Same principle. That checks out with my manual version (which was the thing in code tags), they always return the same thing (unless I've done my math wrong in the manual version, which happens a lot. But I correct it eventually =P). Either I'm missing some mathematical steps (which is possible) or I'm not finding the right poly. I've tried all the CRC32 ones on Wikipedia, but checking my output against a CRC32 calculator didn't work. Here's my JavaScript source:

HTML Code:

<html>
<!--------------------------------------------------------->
<head>
<title>CRC Calculator</title>

<script language="JavaScript">

	// first run of the CRC function
	var first_run = true;
	// remove the implicit 1? (vs is it already removed)
	var imp = true;
	// the original divisor length.. necessary for padding 0s
	var div_length = 0;
	// how done is it?
	var done = new Array(false,false,false);
	// is the entire thing finished?
	var complete = false;

	// divisor/poly (without the implicit bit)
	var divisor = "";
	// register (CRC so far)
	var register = "";
	// binary code of current character
	var binary = "";

	// the reg text field output
	var reg_output;
	// the bin text field output
	var bin_output;
	// the table
	var table;
	// the input text
	var file;

	// pad a string to a certain length
	function pad(input,length,front)
	{
		while(input.length < length)
		{
			if(front)input = "0"+input;
			else input += "0";
		}

		return input;
	}
	function XOR(no1,no2)
	{
		var xored = "";
		//convert them both to binary
		no1 = no1.toString(2);
		no2 = no2.toString(2);
		// switch them if no1 is longer
		if(no1.length < no2.length)
		{
			var temp = no1;
			no1 = no2;
			no2 = temp;
		}

		// go from the lowest to highest value bits until one string runs out
		for(var move_up=1;move_up <= no1.length && move_up <= no2.length;++move_up)
		{
			// if the bits are the same, add a 0 to the beginning of xored, otherwise add a 1
			if(no1.substr(no1.length-move_up,1) == no2.substr(no2.length-move_up,1)) xored = "0"+xored;
			else xored = "1"+xored;
		}
		// once one string runs out, just tack the remaining stuff on the beginning of xored
		for(var keep_going=no1.length-no2.length;keep_going>0;--keep_going)
		{
			xored = no1.substr(keep_going-1,1) + xored;
		}

		// convert to base 10 and return
		return xored;
	}
	function crc()
	{
		var focus = "";

		// if it is the first time, set everything up
		if(first_run)
		{
			// set it to not the first time
			first_run = !first_run;
			// get the divisor
			divisor = document.getElementById("poly").value;
			// if it's in hex, get it in hex
			if(divisor.substring(0,2) == "0x") divisor = parseInt(divisor.substring(2,divisor.length),16);
			else divisor = parseInt(divisor,2);
			// reset the done variables
			done[0] = false;
			done[1] = false;
			done[2] = false;

			// get the length of the divisor
			div_length = divisor.toString(2).length;
		}

		// if the binary has been pushed to the point where we need more...
		if(binary.length < div_length)
		{
			// if there are no chracters left, then we are done with the file
			if(file.innerHTML.length == 0) done[0] = true;

			// if we are not done getting characters from the input
			if(!done[0])
			{
				// get the binary string from the next character in line...
				binary += pad(file.innerHTML.charCodeAt(0).toString(2),8,true);
				// ...and take that character off the assembly line
				file.innerHTML = file.innerHTML.substring(1,file.innerHTML.length);
			}
			// if we have not already appended the extra 0s
			else if(!done[1])
			{
				done[1] = true;
				// append
				for(var append=0;append<div_length-1;++append)
				{
					binary += "0";
				}
			}
			// if we are completely done
			else
			{
				done[2] = true;
				binary = "DONE";
				first_run = true;
			}
		}
		// unless we are completely done
		else if(!done[2])
		{
			// get the first bit (the highest magnitude bit)
			focus = binary.substr(0,1);

			var toggle = 0;

			// if the focused bit is 1, XOR the binary with the divisor
			if(focus == 1) toggle = pad(divisor.toString(2),binary.toString(2).length,false);
			binary = XOR(binary,toggle);

			// now take off the focused bit
			binary = binary.substring(1,binary.length);

			// set the current CRC to the binary
			register = binary;
		}

		// output the current binary
		bin_output.value = binary;
		// output the current CRC
		reg_output.value = "0x"+pad(parseInt(register,2).toString(16).toUpperCase(),Math.ceil((div_length-1)/4),true);

		if(!done[2]) crc();
	}
	// initialize function for when the page loads
	function init()
	{
		// set all the variables that point to stuff in the page
		reg_output = document.getElementById("reg");
		bin_output = document.getElementById("bin");
		table = document.getElementById("organize");
		file = document.getElementById("file");
	}

</script>

</head>
<!--------------------------------------------------------->
<body onload="init()">

	<table id="organize" border="0" align="center">
		<tr>
			<td align="left" onClick="toggle_imp()">Polynomial/Divisor (including implicit 1)</td>
			<td align="center">Binary of current character</td>
			<td align="right">Current CRC</td>
		</tr>
		<tr>
			<td align="left"><input type="text" id="poly" value="11100" size="40" /></td>
			<td align="center"><input type="text" id="bin" value="" /></td>
			<td align="right"><input type="text" id="reg" value="" size="40" /></td>
		</tr>
		<tr>
			<td colspan="3" align="center"><hr />Input text</td>
		</tr>
		<tr>
			<td align="left"></td>
			<td align="center"><textarea id="file" cols="75" rows="33">g</textarea></td>
			<td align="right"></td>
		</tr>
		<tr>
			<td align="left"></td>
			<td align="center"><input type="button" id="button" onClick="crc()" value="Start" /></td>
			<td align="right"></td>
		</tr>
	</table>

</body>
<!--------------------------------------------------------->
</html>

So that seems to work with my manual math. but trying all the CRC32 polys from Wikipedia and comparing my results to a CRC32 calculator got different results. Very annoying. Any help would.. help..

(hopefully) thanks

**WingedPanther** · #2 (**permalink**) 04-21-2008, 10:28 AM

If you run this under FireFox with the Firebug addon, you will be able to step through your code and see if it is actually doing what your manual calculations say should happen.

**Xav** · #3 (**permalink**) 04-21-2008, 01:38 PM

Or you can use the debugger in VWD (Visual Web Developer 2008 Express Edition).

RobotGymnast · #4 (**permalink**) 04-21-2008, 03:02 PM

As I said. it's doing the calculations right. It doesn't work when I compare it to a CRC32 calculator though. It actually seems a bit buggy, but yeah at least with short input it checks out with my manual math

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Nortan Popup Blocker + JavaScript Issue	twalters84	JavaScript and CSS	3	03-11-2008 04:47 AM
PHP accessing through remotely javascript from another website	deny	Request Services (Paid)	4	01-28-2008 08:02 AM
[Easy as Pie] Unobtrusive JavaScript	Kernel	Programming News	0	12-20-2007 09:07 AM
Counting Files with JavaScript	Matt	JavaScript and CSS	5	08-01-2007 12:02 PM

Xav	........	164.00000
dargueta	........	128.00000
John	........	127.00000
gaylo565	........	18.00000
XaNaX	........	15.00000
Johnnyboy	........	3.00000
navghost	........	1.00000

CodeCall

Contest Stats

Sponsors

Ads

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)