Isolating Characters in an Image in JavaScript

The JavaScript program below first draws horizontal separators between lines of text in an imported image, and then draws separators between individual characters in each line. Along with a few other recent posts, it is intended as the beginnings of a system for optical character recognition. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript.


<html>
<body>

<!-- ui -->

<div id="divUI">

	<label><b>Image Characterizer</b></label>
	<p>Load a file, specify a background color, and click the button to automatically split into lines and characters.</p>
	
	<div>
		<label>Image to Find Characters in:</label>
		<input type="file" onchange="inputImageToCharacterize_Changed(this);"></input>
		<div id="divDisplayImageToCharacterize">[none]</div>
	</div>

	<div>
		</div>
			<label>Background Color RGB:</label>
			<input id="inputColorBackground" value="255,255,255"></input>
		</div>
		<div>
			<label>Color Difference Threshold:</label>
			<input id="inputColorDifferenceThreshold" type="number" value="256"></input>
		</div>
		<button onclick="buttonImageCharacterize_Clicked();">Find Characters</button>
	</div>

	<div>
		<label>Image with Characters Highlighted:</label>
		<div id="divDisplayImageCharacterized">[none]</div>
	</div>

</div>

<!-- ui ends-->

<script type="text/javascript">

// ui events

function buttonImageCharacterize_Clicked()
{
	var divDisplayImageToCharacterize = 
		document.getElementById("divDisplayImageToCharacterize");

	var imageToCharacterizeAsCanvas = 
		divDisplayImageToCharacterize.getElementsByTagName("canvas")[0];

	if (imageToCharacterizeAsCanvas == null)
	{
		alert("No image loaded!");
		return;
	}

	var inputColorBackground = 
		document.getElementById("inputColorBackground");
	var inputColorDifferenceThreshold = 
		document.getElementById("inputColorDifferenceThreshold");

	var colorBackground = inputColorBackground.value;
	var colorDifferenceThreshold = inputColorDifferenceThreshold.value;

	var imageCharacterizedAsCanvas = new ImageAutoCharacterizer().findCharactersInCanvas
	(
		imageToCharacterizeAsCanvas,
		colorBackground,
		colorDifferenceThreshold
	);
	imageCharacterizedAsCanvas.style = "border:1px solid";

	var divDisplayImageCharacterized = 
		document.getElementById("divDisplayImageCharacterized");
	divDisplayImageCharacterized.innerHTML = "";
	divDisplayImageCharacterized.appendChild(imageCharacterizedAsCanvas);
}

function inputImageToCharacterize_Changed(input)
{
	var file = input.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(eventFileLoaded)
	{
		var imageAsDataURL = eventFileLoaded.target.result;
		var imageAsDOMElement = document.createElement("img");
		imageAsDOMElement.onload = function(eventImageLoaded)
		{
			var imageAsCanvas = document.createElement("canvas");
			imageAsCanvas.style = "border:1px solid";
			imageAsCanvas.width = imageAsDOMElement.width;
			imageAsCanvas.height = imageAsDOMElement.height;

			var graphics = imageAsCanvas.getContext("2d");
			graphics.drawImage(imageAsDOMElement, 0, 0);

			imageAsCanvas.onmousedown = function(mouseEvent)
			{
				var x = mouseEvent.x;
				var y = mouseEvent.y;

				var pixelRGBA = graphics.getImageData
				(
					x, y, 1, 1
				).data;

				var pixelAsString = 
					+ pixelRGBA[0] + ","
					+ pixelRGBA[1] + ","
					+ pixelRGBA[2]

				var inputColorBackground = 
					document.getElementById("inputColorBackground");

				inputColorBackground.value = pixelAsString;
			}

			var divDisplayImageToCharacterize = document.getElementById
			(
				"divDisplayImageToCharacterize"
			);
			divDisplayImageToCharacterize.innerHTML = "";
			divDisplayImageToCharacterize.appendChild
			(
				imageAsCanvas
			);
		}
		imageAsDOMElement.src = imageAsDataURL;
	}
	fileReader.readAsDataURL(file);
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.prototype.size = function()
	{
		return this.max.clone().subtract(this.min);
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.dimension = function(dimensionIndex, valueToSet)
	{
		return (dimensionIndex == 0 ? this.x : this.y);
	}

	Coords.prototype.dimensionSet = function(dimensionIndex, valueToSet)
	{
		if (dimensionIndex == 0)
		{
			this.x = valueToSet;
		}
		else
		{
			this.y = valueToSet;
		}

		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function ImageAutoCharacterizer()
{
	// do nothing
}
{
	ImageAutoCharacterizer.prototype.findCharactersInCanvas = function
	(
		imageToFindCharactersInAsCanvas,
		colorBackground,
		colorDifferenceThreshold,
	)
	{
		// Draw the image itself.

		var imageCharacterizedAsCanvas = document.createElement("canvas");

		var imageSize = new Coords
		(
			imageToFindCharactersInAsCanvas.width,
			imageToFindCharactersInAsCanvas.height
		);

		imageCharacterizedAsCanvas.width = imageSize.x;
		imageCharacterizedAsCanvas.height = imageSize.y;

		graphics = imageCharacterizedAsCanvas.getContext("2d");
		graphics.drawImage
		(
			imageToFindCharactersInAsCanvas, 
			0, 0
		);

		// Locate the spaces between lines of text.

		var spacesBetweenLinesOfText = this.findSpacesInCanvasInBounds
		(
			imageToFindCharactersInAsCanvas,
			new Bounds(new Coords(0, 0), imageSize),
			colorBackground,
			colorDifferenceThreshold,
			1 // axisI = y
		);

		var lineGroups = 
		[
			spacesBetweenLinesOfText
		];

		for (var i = 0; i < spacesBetweenLinesOfText.length - 1; i++)
		{
			var lineTop = spacesBetweenLinesOfText[i];
			var lineBottom = spacesBetweenLinesOfText[i + 1];

			var spacesBetweenCharactersInLine = this.findSpacesInCanvasInBounds
			(
				imageToFindCharactersInAsCanvas,
				new Bounds(lineTop.fromPos, lineBottom.toPos),
				colorBackground,
				colorDifferenceThreshold,
				0 // axisI = x
			);

			lineGroups.push(spacesBetweenCharactersInLine);			
		}		

		// Draw all the lines.

		graphics.strokeStyle = "Cyan";

		for (var g = 0; g < lineGroups.length; g++)
		{
			var linesInGroup = lineGroups[g];

			for (var i = 0; i < linesInGroup.length; i++)
			{
				var line = linesInGroup[i];

				line.drawToGraphics(graphics);
			}
		}

		return imageCharacterizedAsCanvas;

	}

	ImageAutoCharacterizer.prototype.findSpacesInCanvasInBounds = function
	(	
		imageToSplitAsCanvas,
		bounds,
		colorBackground,
		colorDifferenceThreshold,
		axisI
	)
	{			
		var colorBackgroundRGB = colorBackground.split(",");

		var graphics = imageToSplitAsCanvas.getContext("2d");

		var imageToSplitSize = new Coords
		(
			imageToSplitAsCanvas.width,
			imageToSplitAsCanvas.height
		);

		var pixelPos = new Coords();

		var linesOpen = [];

		var axisJ = 1 - axisI;

		var min = bounds.min;
		var max = bounds.max;

		var iMin = min.dimension(axisI);
		var iMax = max.dimension(axisI);

		var jMin = min.dimension(axisJ);
		var jMax = max.dimension(axisJ);

		for (var i = iMin; i < iMax; i++)
		{
			pixelPos.dimensionSet(axisI, i);

			var isLineOpen = true;
				
			for (var direction = 0; direction < 2; direction++)
			{
				var jStart = (direction == 0 ? jMin : jMax - 1);
				var jEnd = (direction == 0 ? jMax : jMin - 1);
				var jStep = (direction == 0 ? 1 : -1);

				for (var j = jStart; j != jEnd; j += jStep)
				{
 					pixelPos.dimensionSet(axisJ, j);
	
					var isPixelWithinThreshold = 
						this.isPixelWithinThreshold
						(
							graphics, 
							colorBackgroundRGB, 
							colorDifferenceThreshold, 
							pixelPos
						);

					if (isPixelWithinThreshold == false)
					{
						isLineOpen = false;

						break;
					}

				} // end for j

				if (isLineOpen == false)
				{
					break;
				}

			} // end for d

			if (isLineOpen == true)
			{
				var lineOpen = new Line
				(
					new Coords().dimensionSet
					(
						axisJ, jMin
					).dimensionSet
					(
						axisI, i
					),
					new Coords().dimensionSet
					(
						axisJ, jMax
					).dimensionSet
					(
						axisI, i
					)
				);

				linesOpen.push(lineOpen);
			}
		
		} // end for i

		var lineGroupCurrent = [];
		var lineGroups = [];
		var linePrev = null;

		for (var i = 0; i < linesOpen.length; i++)
		{
			var line = linesOpen[i];

			if (linePrev != null)
			{
				var distanceBetweenLineAndPrev = 
					line.fromPos.dimension(axisI) 
					- linePrev.fromPos.dimension(axisI);

				if (distanceBetweenLineAndPrev > 1)
				{
					lineGroups.push(lineGroupCurrent);
					lineGroupCurrent = [];	
				}
			}

			lineGroupCurrent.push(line);

			linePrev = line;
		}

		lineGroups.push(lineGroupCurrent);

		var linesSpaced = [];

		for (var g = 0; g < lineGroups.length; g++)
		{
			var lineGroup = lineGroups[g];

			var indexOfLineAtCenterOfGroup 
				= Math.floor(lineGroup.length / 2);

			var lineAtCenterOfGroup = lineGroup[indexOfLineAtCenterOfGroup];

			linesSpaced.push(lineAtCenterOfGroup);
		}

		var linesForSpaces = linesSpaced;

		return linesForSpaces;
	}

	ImageAutoCharacterizer.prototype.isPixelWithinThreshold = function
	(
		graphics, colorBackgroundRGB, colorDifferenceThreshold, pixelPos
	)
	{
		var isPixelWithinThreshold = false;

		var pixelRGB = graphics.getImageData
		(
			pixelPos.x, pixelPos.y, 1, 1
		).data;

		var pixelDifference = 0;
		var numberOfColorComponents = 3; // rgb

		for (var c = 0; c < numberOfColorComponents; c++)
		{
			var componentDifference = Math.abs
			(
				pixelRGB[c] - colorBackgroundRGB[c]
			);
			pixelDifference += componentDifference;
		}

		var isPixelWithinThreshold =  
			(pixelDifference <= colorDifferenceThreshold);

		return isPixelWithinThreshold;
	}
}

function Line(fromPos, toPos)
{
	this.fromPos = fromPos;
	this.toPos = toPos;
}
{
	Line.prototype.drawToGraphics = function(graphics)
	{
		graphics.beginPath();
		graphics.moveTo(this.fromPos.x, this.fromPos.y);
		graphics.lineTo(this.toPos.x, this.toPos.y);
		graphics.stroke();
	}
}

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , , , | Leave a comment

Drawing Rules Between Lines of Text in Javascript

The JavaScript program below will automatically draw rules between lines of text in a loaded image. It is intended as an early step in an optical character recognition system. To see it in action, copy it into a .html file and open that file in a web browser that runs JavaScript.


<html>
<body>

<!-- ui -->

<div id="divUI">

	<label><b>Image "Rulifier"</b></label>
	<p>Load a file, specify a background color, and click the button to add ruled lines to it.</p>
	
	<div>
		<label>Image to Add Ruled Lines to:</label>
		<input type="file" onchange="inputImageToRule_Changed(this);"></input>
		<div id="divDisplayImageToRule">[none]</div>
	</div>

	<div>
		</div>
			<label>Background Color RGB:</label>
			<input id="inputColorBackground" value="255,255,255"></input>
		</div>
		<div>
			<label>Color Difference Threshold:</label>
			<input id="inputColorDifferenceThreshold" value="0"></input>
		</div>
		<button onclick="buttonImageRule_Clicked();">Add Ruled Lines</button>
	</div>

	<div>
		<label>Image with Ruled Lines:</label>
		<div id="divDisplayImageRuled">[none]</div>
	</div>

</div>

<!-- ui ends-->

<script type="text/javascript">

// ui events

function buttonImageRule_Clicked()
{
	var divDisplayImageToRule = 
		document.getElementById("divDisplayImageToRule");

	var imageToRuleAsCanvas = 
		divDisplayImageToRule.getElementsByTagName("canvas")[0];

	if (imageToRuleAsCanvas == null)
	{
		alert("No image loaded!");
		return;
	}

	var inputColorBackground = 
		document.getElementById("inputColorBackground");
	var inputColorDifferenceThreshold = 
		document.getElementById("inputColorDifferenceThreshold");

	var colorBackground = inputColorBackground.value;
	var colorDifferenceThreshold = inputColorDifferenceThreshold.value;

	var imageRuledAsCanvas = new ImageAutoRulifier().ruleCanvas
	(
		imageToRuleAsCanvas,
		colorBackground,
		colorDifferenceThreshold
	);
	imageRuledAsCanvas.style = "border:1px solid";

	var divDisplayImageRuled = 
		document.getElementById("divDisplayImageRuled");
	divDisplayImageRuled.innerHTML = "";
	divDisplayImageRuled.appendChild(imageRuledAsCanvas);
}

function inputImageToRule_Changed(input)
{
	var file = input.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(eventFileLoaded)
	{
		var imageAsDataURL = eventFileLoaded.target.result;
		var imageAsDOMElement = document.createElement("img");
		imageAsDOMElement.onload = function(eventImageLoaded)
		{
			var imageAsCanvas = document.createElement("canvas");
			imageAsCanvas.style = "border:1px solid";
			imageAsCanvas.width = imageAsDOMElement.width;
			imageAsCanvas.height = imageAsDOMElement.height;

			var graphics = imageAsCanvas.getContext("2d");
			graphics.drawImage(imageAsDOMElement, 0, 0);

			imageAsCanvas.onmousedown = function(mouseEvent)
			{
				var x = mouseEvent.x;
				var y = mouseEvent.y;

				var pixelRGBA = graphics.getImageData
				(
					x, y, 1, 1
				).data;

				var pixelAsString = 
					+ pixelRGBA[0] + ","
					+ pixelRGBA[1] + ","
					+ pixelRGBA[2]

				var inputColorBackground = 
					document.getElementById("inputColorBackground");

				inputColorBackground.value = pixelAsString;
			}

			var divDisplayImageToRule = document.getElementById
			(
				"divDisplayImageToRule"
			);
			divDisplayImageToRule.innerHTML = "";
			divDisplayImageToRule.appendChild
			(
				imageAsCanvas
			);
		}
		imageAsDOMElement.src = imageAsDataURL;
	}
	fileReader.readAsDataURL(file);
}

// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.dimension = function(dimensionIndex, valueToSet)
	{
		var returnValue;

		if (valueToSet == null)		
		{
			returnValue = (dimensionIndex == 0 ? this.x : this.y);
		}
		else 
		{
			if (dimensionIndex == 0)
			{
				this.x = valueToSet;
			}
			else
			{
				this.y = valueToSet;
			}
		}

		return returnValue;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function ImageAutoRulifier()
{
	// do nothing
}
{
	ImageAutoRulifier.prototype.ruleCanvas = function
	(
		imageToRuleAsCanvas,
		colorBackground,
		colorDifferenceThreshold
	)
	{			
		var colorBackgroundRGB = colorBackground.split(",");

		var graphics = imageToRuleAsCanvas.getContext("2d");

		var imageToRuleSize = new Coords
		(
			imageToRuleAsCanvas.width,
			imageToRuleAsCanvas.height
		);

		var pixelPos = new Coords();

		var numberOfAxes = 2;

		var linesOpen = [];

		// hack - Start at 1 to just check the horizontal lines.
		for (var axis0 = 1; axis0 < numberOfAxes; axis0++)
		{
			var axis1 = 1 - axis0;

			var sizeAlongAxis0 = imageToRuleSize.dimension(axis0);
			var sizeAlongAxis1 = imageToRuleSize.dimension(axis1);

			for (var i = 0; i < sizeAlongAxis0; i++)
			{
				pixelPos.dimension(axis0, i);

				var isLineOpen = true;
				
				for (var direction = 0; direction < 2; direction++)
				{
					var jStart = (direction == 0 ? 0 : sizeAlongAxis1 - 1);
					var jEnd = (direction == 0 ? sizeAlongAxis1 : -1);
					var jStep = (direction == 0 ? 1 : -1);

					for (var j = jStart; j != jEnd; j += jStep)
					{
	 					pixelPos.dimension(axis1, j);
	
						var isPixelWithinThreshold = 
							this.ruleCanvas_IsPixelWithinThreshold
							(
								graphics, 
								colorBackgroundRGB, 
								colorDifferenceThreshold, 
								pixelPos
							);

						if (isPixelWithinThreshold == false)
						{
							isLineOpen = false;

							break;
						}

					} // end for j

					if (isLineOpen == false)
					{
						break;
					}

				} // end for d

				if (isLineOpen == true)
				{
					var lineOpen = new Line
					(
						new Coords(0, i),
						new Coords(sizeAlongAxis1, i)
					);

					linesOpen.push(lineOpen);
				}
		
			} // end for i

		} // end for a

		var lineGroupCurrent = [];
		var lineGroups = [];
		var linePrev = linesOpen[0];

		for (var i = 1; i < linesOpen.length; i++)
		{
			var line = linesOpen[i];

			var distanceBetweenLineAndPrev = 
				line.fromPos.y - linePrev.fromPos.y;

			if (distanceBetweenLineAndPrev > 1)
			{
				lineGroups.push(lineGroupCurrent);
				lineGroupCurrent = [];	
			}

			lineGroupCurrent.push(line);

			linePrev = line;
		}

		var linesSpaced = [];

		for (var g = 0; g < lineGroups.length; g++)
		{
			var lineGroup = lineGroups[g];

			var indexOfLineAtCenterOfGroup 
				= Math.floor(lineGroup.length / 2);

			var lineAtCenterOfGroup = lineGroup[indexOfLineAtCenterOfGroup];

			linesSpaced.push(lineAtCenterOfGroup);
		}

		var linesForRules = linesSpaced;

		var imageRuledAsCanvas = document.createElement("canvas");

		var imageRuledSize = imageToRuleSize;

		imageRuledAsCanvas.width = imageRuledSize.x;
		imageRuledAsCanvas.height = imageRuledSize.y;

		graphics = imageRuledAsCanvas.getContext("2d");
		graphics.drawImage
		(
			imageToRuleAsCanvas, 
			0, 0
		);

		graphics.strokeStyle = "Cyan";

		for (var i = 0; i < linesForRules.length; i++)
		{
			var line = linesForRules[i];
			graphics.beginPath();
			graphics.moveTo(line.fromPos.x, line.fromPos.y);
			graphics.lineTo(line.toPos.x, line.toPos.y);
			graphics.stroke();
		}

		return imageRuledAsCanvas;
	}

	ImageAutoRulifier.prototype.ruleCanvas_IsPixelWithinThreshold = function
	(
		graphics, colorBackgroundRGB, colorDifferenceThreshold, pixelPos
	)
	{
		var isPixelWithinThreshold = false;

		var pixelRGB = graphics.getImageData
		(
			pixelPos.x, pixelPos.y, 1, 1
		).data;

		var pixelDifference = 0;
		var numberOfColorComponents = 3; // rgb

		for (var c = 0; c < numberOfColorComponents; c++)
		{
			var componentDifference = Math.abs
			(
				pixelRGB[c] - colorBackgroundRGB[c]
			);
			pixelDifference += componentDifference;
		}

		var isPixelWithinThreshold =  
			(pixelDifference <= colorDifferenceThreshold);

		return isPixelWithinThreshold;
	}
}

function Line(fromPos, toPos)
{
	this.fromPos = fromPos;
	this.toPos = toPos;
}

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , | Leave a comment

An Image Auto-Cropper in JavaScript

The JavaScript program below allows the user to specify an input file, a background color, and a difference threshold, and will automatically crop the image to remove any pixels around its border that match the background color within the specified difference threshold. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

UPDATE 2071/06/22 – The code has been updated to reuse the same code for scanning pixels along both the x and y axes, rather than simply using two different sets of nested loops with identical contents. For efficiency’s sake, the code also now scans each column or row of pixels from both sides, stopping when the first non-croppable pixel is found, rather than scanning the whole line of pixels including the non-croppable ones. A long comment describing this new scanning process in relative detail has also been added.


<html>
<body>

<!-- ui -->

<div id="divUI">

	<label><b>Image Autocropper</b></label>
	<p>Load an image file, click on it to set a background color, set a difference threshold, and click the Crop button.</p>
	
	<div>
		<label>Image to Crop:</label>
		<input type="file" onchange="inputImageToCrop_Changed(this);"></input>
		<div id="divDisplayImageToCrop">[none]</div>
	</div>

	<div>
		</div>
			<label>Background Color RGB:</label>
			<input id="inputColorToCrop" value="255,255,255"></input>
		</div>
		<div>
			<label>Color Difference Threshold:</label>
			<input id="inputColorDifferenceThreshold" value="0"></input>
		</div>
		<button onclick="buttonImageAutocrop_Clicked();">Crop</button>
	</div>

	<div>
		<label>Image Cropped:</label>
		<div id="divDisplayImageCropped">[none]</div>
	</div>

</div>

<!-- ui ends-->

<script type="text/javascript">

// ui events

function buttonImageAutocrop_Clicked()
{
	// todo - validation

	var divDisplayImageToCrop = 
		document.getElementById("divDisplayImageToCrop");
	var inputColorToCrop = 
		document.getElementById("inputColorToCrop");
	var inputColorDifferenceThreshold = 
		document.getElementById("inputColorDifferenceThreshold");

	var imageToCropAsCanvas = 
		divDisplayImageToCrop.getElementsByTagName("canvas")[0];

	var colorToCrop = inputColorToCrop.value;
	var colorDifferenceThreshold = inputColorDifferenceThreshold.value;

	var imageCroppedAsCanvas = new ImageAutocropper().cropCanvas
	(
		imageToCropAsCanvas,
		colorToCrop,
		colorDifferenceThreshold
	);
	imageCroppedAsCanvas.style = "border:1px solid";

	var divDisplayImageCropped = 
		document.getElementById("divDisplayImageCropped");
	divDisplayImageCropped.innerHTML = "";
	divDisplayImageCropped.appendChild(imageCroppedAsCanvas);
}

function inputImageToCrop_Changed(input)
{
	var file = input.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(eventFileLoaded)
	{
		var imageAsDataURL = eventFileLoaded.target.result;
		var imageAsDOMElement = document.createElement("img");
		imageAsDOMElement.onload = function(eventImageLoaded)
		{
			var imageAsCanvas = document.createElement("canvas");
			imageAsCanvas.style = "border:1px solid";
			imageAsCanvas.width = imageAsDOMElement.width;
			imageAsCanvas.height = imageAsDOMElement.height;

			var graphics = imageAsCanvas.getContext("2d");
			graphics.drawImage(imageAsDOMElement, 0, 0);

			imageAsCanvas.onmousedown = function(mouseEvent)
			{
				var x = mouseEvent.x;
				var y = mouseEvent.y;

				var pixelRGBA = graphics.getImageData
				(
					x, y, 1, 1
				).data;

				var pixelAsString = 
					+ pixelRGBA[0] + ","
					+ pixelRGBA[1] + ","
					+ pixelRGBA[2]

				var inputColorToCrop = 
					document.getElementById("inputColorToCrop");

				inputColorToCrop.value = pixelAsString;
			}

			var divDisplayImageToCrop = document.getElementById
			(
				"divDisplayImageToCrop"
			);
			divDisplayImageToCrop.innerHTML = "";
			divDisplayImageToCrop.appendChild
			(
				imageAsCanvas
			);
		}
		imageAsDOMElement.src = imageAsDataURL;
	}
	fileReader.readAsDataURL(file);
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.prototype.size = function()
	{
		return this.max.clone().subtract(this.min);
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.dimension = function(dimensionIndex, valueToSet)
	{
		var returnValue;

		if (valueToSet == null)		
		{
			returnValue = (dimensionIndex == 0 ? this.x : this.y);
		}
		else 
		{
			if (dimensionIndex == 0)
			{
				this.x = valueToSet;
			}
			else
			{
				this.y = valueToSet;
			}
		}

		return returnValue;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function ImageAutocropper()
{
	// do nothing
}
{
	ImageAutocropper.prototype.cropCanvas = function
	(
		imageToCropAsCanvas,
		colorToCrop,
		colorDifferenceThreshold
	)
	{			
		var cropBounds = this.cropCanvas_FindBounds
		(
			imageToCropAsCanvas,
			colorToCrop,
			colorDifferenceThreshold
		);

		var imageCroppedAsCanvas = document.createElement("canvas");

		var imageCroppedSize = cropBounds.size();

		imageCroppedAsCanvas.width = imageCroppedSize.x;
		imageCroppedAsCanvas.height = imageCroppedSize.y;

		var graphics2 = imageCroppedAsCanvas.getContext("2d");
		graphics2.drawImage
		(
			imageToCropAsCanvas, 
			// source rectangle
			cropBounds.min.x, cropBounds.min.y,
			imageCroppedSize.x, imageCroppedSize.y,
			// target rectangle
			0, 0, 
			imageCroppedSize.x, imageCroppedSize.y
		);

		return imageCroppedAsCanvas
	}

	ImageAutocropper.prototype.cropCanvas_FindBounds = function
	(
		imageToCropAsCanvas,
		colorToCrop,
		colorDifferenceThreshold
	)
	{
		var colorToCropRGB = colorToCrop.split(",");

		var graphics = imageToCropAsCanvas.getContext("2d");

		var imageToCropSize = new Coords
		(
			imageToCropAsCanvas.width,
			imageToCropAsCanvas.height
		);

		var cropBounds = new Bounds
		(
			imageToCropSize.clone(),
			new Coords(0, 0)
		);

		// We start with the upper-left pixel,
		// and go down until we find a "non-croppable" pixel outside the threshold.
		// When that happens, we expand the top bound if necessary,
		// then jump to the bottom pixel in the column,
		// and proceed upward until, again, a pixel outside the threshold is found.
		// This time we expand the bottom bound if necessary.
		// Then we go to the top of the next column of pixels,
		// and repeat the top-down and bottom-up loops for each column,
		// expanding the bounds as necessary
		// so that they include all known non-croppable pixels.
		// Then we switch axes from top-to-bottom to left-to-right 
		// and repeat to set the left and right bounds.

		var pixelPos = new Coords();

		var numberOfAxes = 2;

		for (var a0 = 0; a0 < numberOfAxes; a0++)
		{
			var a1 = 1 - a0;

			var sizeAlongAxis0 = imageToCropSize.dimension(a0);
			var sizeAlongAxis1 = imageToCropSize.dimension(a1);

			for (var i = 0; i < sizeAlongAxis0; i++)
			{
				pixelPos.dimension(a0, i);

				for (var d = 0; d < 2; d++)
				{
					var jStart = (d == 0 ? 0 : sizeAlongAxis1 - 1);
					var jEnd = (d == 0 ? sizeAlongAxis1 : -1);
					var jStep = (d == 0 ? 1 : -1);

					for (var j = jStart; j != jEnd; j += jStep)
					{
	 					pixelPos.dimension(a1, j);
	
						var isPixelWithinThreshold = 
							this.cropCanvas_FindBounds_IsPixelWithinThreshold
							(
								graphics, 
								colorToCropRGB, 
								colorDifferenceThreshold, 
								pixelPos
							);

						if (isPixelWithinThreshold == false)
						{
							this.cropCanvas_FindBounds_BoundsExpand
							(
								cropBounds, pixelPos
							);

							break;
						}

					} // end for j

				} // end for d
		
			} // end for i

		} // end for a

		return cropBounds;
	}

	ImageAutocropper.prototype.cropCanvas_FindBounds_IsPixelWithinThreshold = function
	(
		graphics, colorToCropRGB, colorDifferenceThreshold, pixelPos
	)
	{
		var isPixelWithinThreshold = false;

		var pixelRGB = graphics.getImageData
		(
			pixelPos.x, pixelPos.y, 1, 1
		).data;

		var pixelDifference = 0;
		var numberOfColorComponents = 3; // rgb

		for (var c = 0; c < numberOfColorComponents; c++)
		{
			var componentDifference = Math.abs
			(
				pixelRGB[c] - colorToCropRGB[c]
			);
			pixelDifference += componentDifference;
		}

		var isPixelWithinThreshold =  
			(pixelDifference <= colorDifferenceThreshold);

		return isPixelWithinThreshold;
	}

	ImageAutocropper.prototype.cropCanvas_FindBounds_BoundsExpand = function
	(
		cropBounds, pixelPos
	)
	{
		if (pixelPos.x < cropBounds.min.x)
		{
			cropBounds.min.x = pixelPos.x;
		}

		if (pixelPos.x > cropBounds.max.x)
		{
			cropBounds.max.x = pixelPos.x;
		}

		if (pixelPos.y < cropBounds.min.y)
		{
			cropBounds.min.y = pixelPos.y;
		}

		if (pixelPos.y > cropBounds.max.y)
		{
			cropBounds.max.y = pixelPos.y;
		}

		return cropBounds;
	}

}

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , , | Leave a comment

An Image Tagger in JavaScript

The JavaScript program below, when run, prompts the user to load an image file and allows the creation and editing of one or more rectangular “tags” with arbitrary size, color, and text. It also allows the user to convert the tagged image to a JSON file and back, which affords a primitive means to save and load the data.

To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.


<html>
<body>

<!-- ui -->

<div id="divImageTagger">

	<label><b>Image Tagger</b></label>
	<p>Load an image from a file or from JSON text.  Use the arrow keys to move the cursor, holding Shift to move faster.  Press Enter to create a new tag or select an existing one.  Press Enter multiple times to cycle through overlapping tags.  Use Shift-Enter to create a new tag within the bounds of an existing one.  Type with a tag selected to add text.  Press Escape to deselect a tag, or Delete to delete it.</p>

	<div>
		<label>Import from Image File:</label>
		<input type="file" onchange="inputImageFile_Changed(this);">
	</div>
	<div>
		<label>Tagged Image Display:</label>
		<div id="divDisplay">
			<label>[none]</label>
		</div>
	</div>
	<div>
		<label>Tag Selected:</label>
		<label>Text:</label>
		<input id="inputTagSelectedText" onchange="inputTagSelectedText_Changed(this);"></input>
		<label>Color:</label>
		<select id="selectTagSelectedColor" onchange="selectTagSelectedColor_Changed(this);">
			<option>Gray</option>
			<option>Red</option
			<option>Orange</option>
			<option>Yellow</option>
			<option>Green</option>
			<option>Blue</option>
			<option>Violet</option>
			<option>White</option>
			<option>Black</option>
		</select>
	</div>	
	<div>
		<button onclick="buttonImageWithTagsToJSON_Clicked();">v Convert Display to JSON v</button>
		<button onclick="buttonImageWithTagsFromJSON_Clicked();">^ Convert JSON to Display ^</button>	
	</div>
	<div>
		<div><label>Tagged Image as JSON:</label></div>
		<textarea id="textareaImageWithTagsAsJSON" cols="40" rows="10"></textarea>
	</div>

</div>	

<!-- ui ends -->

<script type="text/javascript">

// ui events

function inputImageFile_Changed(inputImageFile)
{
	var imageFileToLoad = inputImageFile.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(event2)
	{
		var imageLoadedAsDataURL = event2.target.result;
		var imageLoadedAsDOMElement = document.createElement("img");
		imageLoadedAsDOMElement.onload = function(event3)
		{					
			var imageLoaded = new Image(imageLoadedAsDOMElement);
			var imageWithTags = new ImageWithTags(imageLoaded, []);
			var session = Globals.Instance.session;
			session.imageWithTags = imageWithTags;
			session.initialize();
		}
		imageLoadedAsDOMElement.src = imageLoadedAsDataURL;		
	}
	fileReader.readAsDataURL(imageFileToLoad);
}

function buttonImageWithTagsFromJSON_Clicked()
{
	var textareaImageWithTagsAsJSON = document.getElementById
	(
		"textareaImageWithTagsAsJSON"
	);
	var imageWithTagsAsJSON = textareaImageWithTagsAsJSON.value;
	var imageWithTagsAsJSONObject;
	try
	{
		imageWithTagsAsJSONObject = JSON.parse(imageWithTagsAsJSON);
		var imageWithTags = ImageWithTags.fromJSONObject
		(
			imageWithTagsAsJSONObject,
			// callback
			function (imageWithTags)
			{
				var session = Globals.Instance.session;
				session.imageWithTags = imageWithTags;
				session.initialize();
			}
		);
	}
	catch (err)
	{
		alert("Invalid format!");
	}
}

function buttonImageWithTagsToJSON_Clicked()
{
	var imageWithTags = Globals.Instance.session.imageWithTags;
	if (imageWithTags == null)
	{
		alert("No image loaded!");
	}
	else
	{
		var imageWithTagsAsJSON = imageWithTags.toJSON();
		var textareaImageWithTagsAsJSON = document.getElementById
		(
			"textareaImageWithTagsAsJSON"
		);
		textareaImageWithTagsAsJSON.value = imageWithTagsAsJSON;
	}
}

function inputTagSelectedText_Changed()
{
	var session = Globals.Instance.session;
	var imageWithTags = session.imageWithTags;
	if (imageWithTags != null)
	{
		var tagSelected = session.cursor.tagSelected;
		if (tagSelected != null)
		{
			var inputTagSelectedText = document.getElementById("inputTagSelectedText");
			var text = inputTagSelectedText.value;
			tagSelected.text = text;
			session.update();
		}
	}	
}

function selectTagSelectedColor_Changed()
{
	var session = Globals.Instance.session;
	var imageWithTags = session.imageWithTags;
	if (imageWithTags != null)
	{
		var tagSelected = session.cursor.tagSelected;
		if (tagSelected != null)
		{
			var selectTagSelectedColor = document.getElementById("selectTagSelectedColor");
			var color = selectTagSelectedColor.value;
			tagSelected.color = color;
			session.update();
		}
	}	
}


// main

function main()
{
	var session = new Session();
	Globals.Instance.initialize(session);
}

// extensions 

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.remove = function(element)
	{
		var elementIndex = this.indexOf(element);
		if (elementIndex >= 0)
		{
			this.splice(elementIndex, 1);
		}
		return this;
	}
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.prototype.overlapWith = function(other)
	{
		var returnValue = 
		(
			(
				(
					this.min.x >= other.min.x
					&& this.min.x <= other.max.x
				)
				||
				(
					this.max.x >= other.min.x
					&& this.max.x <= other.max.x
				)
				||
				(
					other.min.x >= this.min.x
					&& other.min.x <= this.max.x
				)
				||
				(
					other.max.x >= this.min.x
					&& other.max.x <= this.max.x
				)
			)
			&&
			(
				(
					this.min.y >= other.min.y
					&& this.min.y <= other.max.y
				)
				||
				(
					this.max.y >= other.min.y
					&& this.max.y <= other.max.y
				)
				||
				(
					other.min.y >= this.min.y
					&& other.min.y <= this.max.y
				)
				||
				(
					other.max.y >= this.min.y
					&& other.max.y <= this.max.y
				)
			)
		);

		return returnValue;
	}	
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	// instances

	Coords.Instances = new Coords_Instances();

	function Coords_Instances()
	{
		this.Zeroes = new Coords(0, 0);
	}

	// methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function Cursor(pos, size)
{
	this.pos = pos;
	this.size = size;

	this.sizeHalf = this.size.clone().divideScalar(2);

	this.tagSelected = null;
}
{
	// constants

	Cursor.Size = new Coords(8, 8);

	// methods

	Cursor.prototype.bounds = function()
	{
		return new Bounds(this.pos, this.pos.clone().add(this.size));
	}

	Cursor.prototype.color = function()
	{
		return (this.tagSelected == null ? "Red" : "Green");
	}

	Cursor.prototype.tagSelect = function(tagToSelect)
	{
		this.tagSelected = tagToSelect;

		if (this.tagSelected != null)
		{
			var inputTagSelectedText = document.getElementById("inputTagSelectedText");
			var selectTagSelectedColor = document.getElementById("selectTagSelectedColor");
		
			inputTagSelectedText.value = this.tagSelected.text;
			selectTagSelectedColor.value = this.tagSelected.color;
		}
	}

	// drawable

	Cursor.prototype.drawToDisplay = function(display)
	{
		display.drawRectangle
		(
			this.pos.clone().subtract(this.sizeHalf), 
			this.size,
			this.color()
		);

		if (this.tagSelected != null)
		{
			this.tagSelected.drawToDisplay(display);
			display.drawRectangle
			(
				this.tagSelected.pos.clone().subtract(this.sizeHalf), 
				this.size,
				"Green"
			)
		}
	}
}

function Display(size)
{
	this.size = size;

	this.colorBack = "White";
	this.colorFore = "Black";

	this.fontHeightInPixels = 10;
	this.font = this.fontHeightInPixels + "px sans-serif";
}
{
	Display.prototype.drawImage = function(image, pos)
	{
		this.graphics.drawImage(image.systemImage, pos.x, pos.y);
	}

	Display.prototype.drawRectangle = function(pos, size, color)
	{
		this.graphics.strokeStyle = color;
		this.graphics.strokeRect(pos.x, pos.y, size.x, size.y);
	}

	Display.prototype.drawText = function(text, pos, color)
	{
		/*
		this.graphics.strokeStyle = (color == "Black" ? "White" : "Black");
		this.graphics.strokeText
		(
			" " + text, 
			pos.x, 
			pos.y + this.fontHeightInPixels
		);
		*/

		this.graphics.fillStyle = color;
		this.graphics.fillText
		(
			" " + text, 
			pos.x, 
			pos.y + this.fontHeightInPixels
		);
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.style = "border:1px solid";
		this.canvas.width = this.size.x;
		this.canvas.height = this.size.y;

		var divDisplay = document.getElementById("divDisplay");
		divDisplay.innerHTML = "";
		divDisplay.appendChild(this.canvas);

		this.graphics = this.canvas.getContext("2d");
		this.graphics.font = this.font;

		this.canvas.tabIndex = 0; // If not set, a canvas can't get focus.
		this.canvas.focus();
	}
}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();

	// methods

	Globals.prototype.initialize = function(session)
	{
		this.session = session;
		this.session.initialize();

		this.inputHelper = new InputHelper();
		this.inputHelper.initialize();
	}
}

function Image(systemImage)
{
	this.systemImage = systemImage;

	this.size = new Coords
	(
		this.systemImage.width, this.systemImage.height
	);
}
{
	Image.prototype.drawToDisplay = function(display)
	{
		display.drawImage(this, Coords.Instances.Zeroes);
	}
}

function ImageWithTags(image, tags)
{
	this.image = image;
	this.tags = tags;
}
{
	ImageWithTags.prototype.tagsInBounds = function(boundsToCheck)
	{
		var returnValues = [];

		for (var i = 0; i < this.tags.length; i++)
		{
			var tag = this.tags[i];
			var tagBounds = tag.bounds();
			if (tagBounds.overlapWith(boundsToCheck) == true)
			{
				returnValues.push(tag);
			}
		}

		return returnValues;
	}

	// drawable

	ImageWithTags.prototype.drawToDisplay = function(display)
	{
		this.image.drawToDisplay(display);

		for (var i = 0; i < this.tags.length; i++)
		{
			var tag = this.tags[i];
			tag.drawToDisplay(display);
		}
	}

	// json

	ImageWithTags.fromJSONObject = function(imageWithTagsAsJSONObject, callback)
	{
		var imageAsDataURL = imageWithTagsAsJSONObject["imageAsDataURL"];

		var tagsAsObjects = imageWithTagsAsJSONObject["tags"];
		var tags = []; // todo
		for (var i = 0; i < tagsAsObjects.length; i++)
		{
			var tagAsObject = tagsAsObjects[i];
			var text = tagAsObject.text;
			var color = tagAsObject.color;
			var posAsObject = tagAsObject.pos;
			var pos = new Coords(posAsObject.x, posAsObject.y);
			var sizeAsObject = tagAsObject.size;
			var size = new Coords(sizeAsObject.x, sizeAsObject.y);
			var tag = new Tag(text, color, pos, size);
			tags.push(tag);
		}

		var systemImage = document.createElement("img");
		systemImage.onload = function(event)
		{
			var image = new Image(systemImage);
			var returnValue = new ImageWithTags(image, tags);
			callback(returnValue);
		}
		systemImage.src = imageAsDataURL;

	}

	ImageWithTags.prototype.toJSON = function(imageWithTagsAsJSON)
	{
		var objectToStringify = 
		{
			tags : this.tags,
			imageAsDataURL : this.image.systemImage.src
		};
		var returnValue = JSON.stringify(objectToStringify, null, 4);

		return returnValue;
	}
}


function InputHelper()
{
	this.keyPressed = null;
	this.isShiftPressed = false;

	this.keysToPreventDefaultActionFor = 
	[
		"Enter", " ",
	];
}
{
	InputHelper.prototype.clear = function()
	{
		this.keyPressed = null;
		this.isShiftPressed = null;
	}

	InputHelper.prototype.initialize = function()
	{
		var body = document.body;
		body.onkeydown = this.handleEventKeyDown.bind(this);
		body.onkeyup = this.handleEventKeyUp.bind(this);
	}

	// events

	InputHelper.prototype.handleEventKeyDown = function(event)
	{		
		var keyPressed = event.key;

		if (this.keysToPreventDefaultActionFor.indexOf(keyPressed) >= 0)
		{
			event.preventDefault();
		}

		this.keyPressed = keyPressed;
		this.isShiftPressed = event.shiftKey;

		var elementActive = document.activeElement;
		var elementActiveTypeName = elementActive.constructor.name;
		if (elementActiveTypeName == "HTMLCanvasElement")
		{		
			Globals.Instance.session.update();
		}
	}

	InputHelper.prototype.handleEventKeyUp = function(event)
	{
		this.keyPressed = null;
	}
}

function Session(imageWithTags)
{
	this.imageWithTags = imageWithTags;
}
{
	Session.prototype.colorSelected = function()
	{
		var selectTagSelectedColor = document.getElementById("selectTagSelectedColor");
		var returnValue = selectTagSelectedColor.value;
		return returnValue;
	}

	Session.prototype.initialize = function()
	{
		if (this.imageWithTags != null)
		{
			var image = this.imageWithTags.image;
			var display = new Display(image.size);	
			display.initialize();
			Globals.Instance.display = display;
			this.cursor = new Cursor(image.size.clone().divideScalar(2), Cursor.Size);

			this.update();
		}			
	}

	Session.prototype.update = function()
	{
		if (this.cursor == null || this.imageWithTags == null)
		{
			return;
		}

		var inputHelper = Globals.Instance.inputHelper;
		var keyPressed = inputHelper.keyPressed;
		var tagSelected = this.cursor.tagSelected;
		var tagAlreadyExisted = (this.imageWithTags.tags.indexOf(tagSelected) >= 0);

		if (this.cursor == null || keyPressed == null)
		{
			// do nothing
		}
		else if (keyPressed == "Enter")
		{
			if (tagSelected == null || tagAlreadyExisted == true)
			{
				var cursorBounds = this.cursor.bounds();
				var tagsAtPos = this.imageWithTags.tagsInBounds(cursorBounds);

				if (tagsAtPos.length == 0 || inputHelper.isShiftPressed == true)
				{
					tagSelected = new Tag
					(
						"", // text
						this.colorSelected(),
						this.cursor.pos.clone(), 
						new Coords(0, 0) // size
					);
				}
				else 
				{			
					var indexOfTagSelected = tagsAtPos.indexOf(tagSelected);
					indexOfTagSelected++;
					
					if (indexOfTagSelected < tagsAtPos.length)
					{
						tagSelected = tagsAtPos[indexOfTagSelected];
					}
					else
					{
						tagSelected = null;
					}
				}
			}
			else
			{
				if (tagSelected.isValid() == true)
				{
					this.imageWithTags.tags.push(tagSelected);
				}
			}

			this.cursor.tagSelect(tagSelected);
		}
		else if (keyPressed == "Escape")
		{
			if (tagSelected != null)
			{
				this.cursor.tagSelected = null;
			}
		}
		else if (keyPressed.startsWith("Arrow") == true)
		{
			if (tagAlreadyExisted == false)
			{
				var cursorMove;

				if (keyPressed == "ArrowDown")
				{
					cursorMove = new Coords(0, 1);
				}
				else if (keyPressed == "ArrowLeft")
				{
					cursorMove = new Coords(-1, 0);
				}
				else if (keyPressed == "ArrowRight")
				{
					cursorMove = new Coords(1, 0);
				}
				else if (keyPressed == "ArrowUp")
				{
					cursorMove = new Coords(0, -1);
				}

				if (inputHelper.isShiftPressed == true)
				{
					cursorMove.multiplyScalar(8);
				}

				this.cursor.pos.add(cursorMove);

				if (tagSelected != null)
				{
					tagSelected.size.add(cursorMove);
				}
			}
		}
		else if (keyPressed == "Delete")
		{
			if (tagSelected != null)
			{
				this.imageWithTags.tags.remove(tagSelected);
				this.cursor.tagSelected = null;
			}
		}
		else if (keyPressed == "Backspace")
		{
			if (tagSelected != null)
			{
				var text = tagSelected.text;
				tagSelected.text = text.substr(0, text.length - 1);
			}
		}
		else if (keyPressed.length == 1)
		{
			if (tagSelected != null)
			{
				tagSelected.text += keyPressed;
			}
		}

		inputHelper.clear();

		this.drawToDisplay(Globals.Instance.display);
	}

	// drawable
	
	Session.prototype.drawToDisplay = function(display)
	{
		if (this.imageWithTags != null)
		{
			this.imageWithTags.drawToDisplay(display);
			this.cursor.drawToDisplay(display);
		}
	}
}

function Tag(text, color, pos, size)
{
	this.text = text;
	this.color = color;
	this.pos = pos;
	this.size = size;
}
{
	Tag.prototype.bounds = function()
	{
		return new Bounds(this.pos, this.pos.clone().add(this.size));
	}

	Tag.prototype.isValid = function()
	{
		return (this.size.magnitude() > 0);
	}

	// drawable

	Tag.prototype.drawToDisplay = function(display)
	{
		display.drawRectangle(this.pos, this.size, this.color);
		display.drawText(this.text, this.pos, this.color);
	}
}

// main

main();

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , | Leave a comment

Comparing Images in JavaScript

The JavaScript code below, when run, prompts the user to specify two image files and click a button to calculate the difference in intensity of their respective pixels. It is intended only as a simple early experiment in the field of optical character recognition.


<html>
<body>

<div id="divUI">

	<div>
		<label>Image 0:</label>
		<input id="inputFileImage0" type="file" onchange="inputFileImage0_Changed(this);"></input>
		<div id="divDisplayImage0"></div>
	</div>	

	<div>
		<label>Image 1:</label>
		<input id="inputFileImage1" type="file" onchange="inputFileImage1_Changed(this);"></input>
		<div id="divDisplayImage1"></div>
	</div>

	<div>
		<button onclick="buttonCompareImages_Clicked();">Compare Images</button>
	</div>

	<div>
		<label>Difference:</label>
		<div id="divDisplayDifference"></div>
		<input id="inputDifference"></input>
	</div>
</div>

<script type="text/javascript">

// ui events

function buttonCompareImages_Clicked()
{
	var divDisplayImage0 = document.getElementById("divDisplayImage0");
	var image0 = divDisplayImage0.getElementsByTagName("img")[0];

	var divDisplayImage1 = document.getElementById("divDisplayImage1");
	var image1 = divDisplayImage1.getElementsByTagName("img")[0];

	if (image0 == null || image1 == null)
	{
		alert("Images not yet loaded!");
	}
	else
	{
		var comparator = new ImageComparator();
		var differenceCanvasAndAmount = comparator.compareImages(image0, image1);

		var differenceCanvas = differenceCanvasAndAmount[0];
		var differenceAmount = differenceCanvasAndAmount[1];

		var divDisplayDifference = document.getElementById("divDisplayDifference");
		divDisplayDifference.appendChild(differenceCanvas);

		var inputDifference = document.getElementById("inputDifference");

		inputDifference.value = differenceAmount;
	}
}

function inputFileImage1_Changed()
{
	inputFileImageN_Changed(1);
}

function inputFileImage0_Changed()
{
	inputFileImageN_Changed(0);
}

function inputFileImageN_Changed(imageNumber)
{
	var input = document.getElementById("inputFileImage" + imageNumber);
	var divDisplay = document.getElementById("divDisplayImage" + imageNumber);

	var file = input.files[0];

	var fileReader = new FileReader();
	fileReader.onload = function(event)
	{
		var fileContentsAsDataURL = event.target.result;
		var imageLoaded = document.createElement("img");
		imageLoaded.src = fileContentsAsDataURL;
		divDisplay.appendChild(imageLoaded);
 	}

	fileReader.readAsDataURL(file);
}

// extensions

function CanvasRenderingContext2DExtensions()
{
	// extension class
}
{
	CanvasRenderingContext2D.prototype.pixelIntensityAtPos = function(pixelPos)
	{
		var imageDataForPixel = this.getImageData
		(
			pixelPos.x, pixelPos.y, 1, 1
		);

		var pixelComponentsAsUint8ClampedArray = imageDataForPixel.data;

		var pixelComponentsRGBA = 
		[
			pixelComponentsAsUint8ClampedArray[0],
			pixelComponentsAsUint8ClampedArray[1],
			pixelComponentsAsUint8ClampedArray[2],
			pixelComponentsAsUint8ClampedArray[3]
		];

		var returnValue = 
			(
				pixelComponentsRGBA[0]
				+ pixelComponentsRGBA[1]
				+ pixelComponentsRGBA[2]
			) 
			/ 3;

		return returnValue;
	}
}

// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}

function ImageComparator()
{
	// do nothing
}
{
	ImageComparator.prototype.compareImages = function(image0, image1)
	{
		var images = [ image0, image1 ];
		var graphicsContextsForImages = [];

		for (var i = 0; i < images.length; i++)
		{
			var image = images[i];
			var imageAsCanvas = document.createElement("canvas");

			imageAsCanvas.width = image.width;
			imageAsCanvas.height = image.height;			

			var graphicsContextForImage = imageAsCanvas.getContext("2d");
			graphicsContextForImage.drawImage(image, 0, 0);

			graphicsContextsForImages.push(graphicsContextForImage);
		}

		var graphicsForImage0 = graphicsContextsForImages[0];
		var graphicsForImage1 = graphicsContextsForImages[1];

		var imageSize = new Coords(image0.width, image0.height);

		var differenceAmountSoFar = 0;

		var canvasDifference = document.createElement("canvas");
		canvasDifference.width = imageSize.x;
		canvasDifference.height = imageSize.y;
		var graphicsDifference = canvasDifference.getContext("2d");

		var pixelPos = new Coords();

		for (var y = 0; y < imageSize.y; y++)
		{
			pixelPos.y = y;
			
			for (var x = 0; x < imageSize.x; x++)
			{
				pixelPos.x = x;

				var image0Pixel = graphicsForImage0.pixelIntensityAtPos(pixelPos);
				var image1Pixel = graphicsForImage1.pixelIntensityAtPos(pixelPos);

				var differenceOfPixels = Math.abs(image0Pixel - image1Pixel);

				differenceAmountSoFar += differenceOfPixels;

				graphicsDifference.fillStyle = 
					"rgb(" 
					+ differenceOfPixels + ", "
					+ differenceOfPixels + ", "
					+ differenceOfPixels
					+ ")";

				graphicsDifference.fillRect(x, y, 1, 1);
			}
		}

		return [canvasDifference, differenceAmountSoFar];
	}
}

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , , | Leave a comment

A Rudimentary Desktop Publishing Application in JavaScript

The code below implements a simple desktop publishing application in JavaScript. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript. Or, for an online version, visit https://thiscouldbebetter.neocities.org/desktoppublisher.html.


<html>
<body>

<!-- ui begins -->

<div>
<label>Document as JSON:</label><br />
<textarea id="textareaDocumentAsJSON" cols="80" rows="32" wrap="off" >
{
	"name":"Invictus",
	"pageSizeInPixels":{"x":300,"y":300},
	"fonts": [ { "name":"sans-serif", "heightInPixels":10 } ],
	"pageDefns":
	[
		{
			"name": "PageDefn0",
			"zoneDefns":
			[
				{ "name":"0", "pos":{"x":10,"y":10}, "size":{"x":150,"y":80}, "margin":{"x":20,"y":20}, "pageOffsetNext":0, "zoneNameNext":"1" },
				{ "name":"1", "pos":{"x":70,"y":110}, "size":{"x":150,"y":80}, "margin":{"x":20,"y":20}, "pageOffsetNext":0,"zoneNameNext":"2" },
				{ "name":"2", "pos":{"x":130,"y":210}, "size":{"x":150,"y":80}, "margin":{"x":20,"y":20}, "pageOffsetNext":1,"zoneNameNext":"0"  }
			]
		}
	],
	"contentBlocks": 
	[
		{ 
			"name": "Content0", 
			"typeName": "text", 
			"data": "Out of the night which covers me, black as the pit from pole to pole, I thank whatever gods may be for my unconquerable soul.\n\nIn the fell clutch of circumstance, I have not winced nor cried aloud.  Under the bludgeoning of chance, my head is bloody, but unbowed.\n\nBeyond this place of wrath and tears looms but the Horror of the shade, and yet the menace of the years finds, and shall find me, unafraid.\n\nIt matters not how strait the gate, how charged with punishments the scroll, I am the master of my fate: I am the captain of my soul.\n\n-William Ernest Henley"
		} 
	],
	"pages": 
	[
		{ "defnName": "PageDefn0" },
		{ "defnName": "PageDefn0" },
		{ "defnName": "PageDefn0" }
	],
	"contentAssignments": 
	[
		{ "contentBlockName":"Content0", "pageIndex":0, "zoneName":"0" }
	]
}
</textarea>
</div>

<div>
	<button onclick="buttonDisplay_Clicked();">Display</button>
	<button onclick="buttonExport_Clicked();">Export</button>
</div>


<!-- ui ends -->

<script type="text/javascript">

// ui events

function buttonDisplay_Clicked()
{
	var documentToDisplay = documentParseAndLayOut();
	documentToDisplay.draw();
}

function buttonExport_Clicked()
{
	var documentToExport = documentParseAndLayOut();
	var documentAsTarFile = documentToExport.toTarFile();
	var documentAsBytes = documentAsTarFile.toBytes();
	FileHelper.saveBytesAsFile(documentAsBytes, documentToExport.name + ".tar");
}

function documentParseAndLayOut()
{
	var textareaDocumentAsJSON = document.getElementById
	(
		"textareaDocumentAsJSON"
	);
	var documentAsStringJSON = textareaDocumentAsJSON.value;
	
	var documentAsDeserializedObject = JSON.parse(documentAsStringJSON);

	var documentParsed = Document.fromDeserializedObject
	(
		documentAsDeserializedObject
	);

	documentParsed.initialize();
	documentParsed.update();

	return documentParsed;
}


// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var key = element[keyName];
			this[key] = element;
		}
	
		return this;
	}
}

function StringExtensions()
{
	// extension class
}
{
	String.prototype.padLeft = function(lengthToPadTo, charToPadWith)
	{
		var returnValue = this;

		while (returnValue.length < lengthToPadTo)
		{
			returnValue = charToPadWith + returnValue;
		}

		return returnValue;
	}


	String.prototype.padRight = function(lengthToPadTo, charToPadWith)
	{
		var returnValue = this;

		while (returnValue.length < lengthToPadTo)
		{
			returnValue += charToPadWith;
		}

		return returnValue;
	}
}

// classes

function ContentAssignment(contentBlockName, pageIndex, zoneDefnName)
{
	this.contentBlockName = contentBlockName;
	this.pageIndex = pageIndex;
	this.zoneDefnName = zoneDefnName;
}
{
	ContentAssignment.fromDeserializedObject = function(contentAssignmentAsObject)
	{
		return new ContentAssignment
		(
			contentAssignmentAsObject.contentBlockName,
			contentAssignmentAsObject.pageIndex,
			contentAssignmentAsObject.zoneName
		);
	}
}

function ContentBlock(name, typeName, data)
{
	this.name = name;
	this.typeName = typeName;
	this.data = data;
}
{
	ContentBlock.fromDeserializedObject = function(contentBlockAsObject)
	{
		return new ContentBlock
		(
			contentBlockAsObject.name,
			contentBlockAsObject.typeName,
			contentBlockAsObject.data
		);
	}
}

function ContentType(name)
{
	this.name = name;
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}

	// serializable

	Coords.fromDeserializedObject = function(coordsAsObject)
	{
		return new Coords(coordsAsObject.x, coordsAsObject.y);
	}
}

function Display(sizeInPixels, renderToScreen)
{
	this.sizeInPixels = sizeInPixels;
	this.renderToScreen = (renderToScreen == null ? true : renderToScreen);

	this.drawPos = new Coords();
}
{
	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			new Coords(0, 0), this.sizeInPixels, "White", "Gray"
		);
	}

	Display.prototype.fontSet = function(font)
	{
		this.font = font;
		this.graphics.font = font.toString();
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.sizeInPixels.x;
		this.canvas.height = this.sizeInPixels.y;
		this.graphics = this.canvas.getContext("2d");

		if (this.renderToScreen == true)
		{
			document.body.appendChild(this.canvas);
		}
	}

	Display.prototype.toImageBytes = function()
	{
		var imageAsPNGDataURL = this.canvas.toDataURL("image/png");

		var imageAsByteString = atob(imageAsPNGDataURL.split(',')[1]);
		var imageAsBytes = [];

		for (var i = 0; i < imageAsByteString.length; i++) 
		{
			var byte = imageAsByteString.charCodeAt(i);
			imageAsBytes.push(byte);
		}

		return imageAsBytes;
	}

	Display.prototype.widthOfText = function(textToMeasure)
	{
		return this.graphics.measureText(textToMeasure).width;
	}

	// primitives

	Display.prototype.drawRectangle = function(pos, size, colorFill, colorBorder)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}

	Display.prototype.drawText = function(text, pos)
	{
		this.graphics.fillStyle = "Gray";
		this.graphics.fillText
		(
			text,
			pos.x, pos.y
		);

		
	}
}

function Document(name, pageSizeInPixels, fonts, pageDefns, contentBlocks, pages, contentAssignments)
{
	this.name = name;
	this.pageSizeInPixels = pageSizeInPixels;
	this.fonts = fonts.addLookups("name");
	this.pageDefns = pageDefns.addLookups("name");
	this.contentBlocks = contentBlocks.addLookups("name");
	this.pages = pages;
	this.contentAssignments = contentAssignments;
}
{
	Document.prototype.initialize = function()
	{
		var pages = this.pages;

		for (var i = 0; i < pages.length; i++)
		{
			var page = pages[i];
			page.initialize(this);
		}		
	}

	Document.prototype.update = function()
	{
		var pages = this.pages;

		for (var i = 0; i < pages.length; i++)
		{
			var page = pages[i];
			page.update(this);
		}		
	}

	// drawable

	Document.prototype.draw = function()
	{
		var pages = this.pages;

		for (var i = 0; i < pages.length; i++)
		{
			var page = pages[i];
			page.draw(this);
		}		
	}
	
	// serializable

	Document.fromDeserializedObject = function(documentAsObject)
	{
		var name = documentAsObject.name;

		var pageSizeInPixels = Coords.fromDeserializedObject
		(
			documentAsObject.pageSizeInPixels
		);

		var fonts = [];
		var fontsAsObjects = documentAsObject.fonts;
		for (var i = 0; i < fontsAsObjects.length; i++)
		{
			var fontAsObject = fontsAsObjects[i];
			var font = new Font(fontAsObject.name, fontAsObject.heightInPixels);
			fonts.push(font);
		}

		var pageDefns = [];
		var pageDefnsAsObjects = documentAsObject.pageDefns;
		for (var i = 0; i < pageDefnsAsObjects.length; i++)
		{
			var pageDefnAsObject = pageDefnsAsObjects[i];
			var pageDefn = PageDefn.fromDeserializedObject(pageDefnAsObject);
			pageDefns.push(pageDefn);
		}

		var contentBlocks = [];
		var contentBlocksAsObjects = documentAsObject.contentBlocks;
		for (var i = 0; i < contentBlocksAsObjects.length; i++)
		{
			var contentBlockAsObject = contentBlocksAsObjects[i];
			var contentBlock = ContentBlock.fromDeserializedObject
			(
				contentBlockAsObject
			);
			contentBlocks.push(contentBlock);
		}

		var pages = [];
		var pagesAsObjects = documentAsObject.pages;
		for (var i = 0; i < pagesAsObjects.length; i++)
		{
			var pageAsObject = pagesAsObjects[i];
			var page = Page.fromDeserializedObject(pageAsObject);
			pages.push(page);
		}

		var contentAssignments = [];
		var contentAssignmentsAsObjects = documentAsObject.contentAssignments;
		for (var i = 0; i < contentAssignmentsAsObjects.length; i++)
		{
			var contentAssignmentAsObject = contentAssignmentsAsObjects[i];
			var contentAssignment = ContentAssignment.fromDeserializedObject(contentAssignmentAsObject);
			contentAssignments.push(contentAssignment);
		}

		var returnValue = new Document
		(
			name,
			pageSizeInPixels,
			fonts,
			pageDefns,
			contentBlocks,
			pages,
			contentAssignments
		);

		return returnValue;
	}

	// tar

	Document.prototype.toTarFile = function()
	{
		var returnValue = TarFile.new();

		for (var i = 0; i < this.pages.length; i++)
		{
			var page = this.pages[i];
			page.draw(this, false);
			var pageAsImageBytes = page.display.toImageBytes();

			var pageAsTarFileEntry = TarFileEntry.fileNew
			(
				"Page" + i + ".png",
				pageAsImageBytes
			);

			returnValue.entries.push(pageAsTarFileEntry);
		}

		return returnValue;
	}

}

function Font(name, heightInPixels)
{
	this.name = name;
	this.heightInPixels = heightInPixels;
}
{
	Font.prototype.toString = function()
	{
		return "" + this.sizeInPixels + "px " + this.name;
	}
}

function Page(defnName, zones)
{
	this.defnName = defnName;
	this.zones = zones;
}
{
	Page.prototype.defn = function(document)
	{
		return document.pageDefns[this.defnName];
	}

	Page.prototype.initialize = function(document)
	{
		this.zonesBuild(document);
	}

	Page.prototype.update = function(document)
	{		
		var defn = this.defn(document);
		var zoneDefns = defn.zoneDefns;

		var contentAssignments = document.contentAssignments;

		var pageIndex = document.pages.indexOf(this);

		for (var i = 0; i < contentAssignments.length; i++)
		{
			var contentAssignment = contentAssignments[i];
			if (pageIndex == contentAssignment.pageIndex)
			{
				var contentBlockName = contentAssignment.contentBlockName;
				var contentBlock = document.contentBlocks[contentBlockName];
				var zoneDefnName = contentAssignment.zoneDefnName;
				var zoneDefn = zoneDefns[zoneDefnName];			
				var zoneIndex = zoneDefns.indexOf(zoneDefn);
				var zone = this.zones[zoneIndex];
				zone.contentBlockName = contentBlockName;
			}
		}

		for (var i = 0; i < this.zones.length; i++)
		{
			var zone = this.zones[i];
			zone.update(document, this);
		}
	}

	Page.prototype.zonesBuild = function(document)
	{
		var defn = this.defn(document);

		if (this.zones == null)
		{
			var zoneDefns = defn.zoneDefns;

			var zones = [];

			for (var i = 0; i < zoneDefns.length; i++)
			{
				var zoneDefn = zoneDefns[i];
				var zone = new Zone(zoneDefn.name);
				zones.push(zone);
			}

			this.zones = zones;
		}
	}

	// drawable

	Page.prototype.draw = function(document, renderToScreen)
	{
		var displaySizeInPixels = document.pageSizeInPixels;
		this.display = new Display(displaySizeInPixels, renderToScreen);
		this.display.initialize();

		this.display.clear();

		var zones = this.zones;

		for (var i = 0; i < zones.length; i++)
		{
			var zone = zones[i];
			zone.draw(document, this);
		}		
	}

	// serializable

	Page.fromDeserializedObject = function(pageAsObject)
	{
		var zones = null;

		var zonesAsObjects = pageAsObject.zones;
		if (zonesAsObjects != null)
		{
			zones = [];

			for (var i = 0; i < zonesAsObjects.length; i++)
			{
				var zoneAsObject = zonesAsObjects[i];
				var zone = Zone.fromDeserializedObject(zoneAsObject);
				zones.push(zone);
			}
		}

		var returnValue = new Page
		(
			pageAsObject.defnName,
			zones
		);

		return returnValue;
	}

}

function PageDefn(name, zoneDefns)
{
	this.name = name;
	this.zoneDefns = zoneDefns.addLookups("name");

	for (var z = 0; z < this.zoneDefns.length; z++)
	{
		var zoneDefn = this.zoneDefns[z];
		var zoneDefnNameNext = zoneDefn.zoneDefnNameNext;
		if (zoneDefnNameNext != null)
		{
			zoneDefnNext = this.zoneDefns[zoneDefnNameNext];
			zoneDefnNext.zoneDefnNamePrev = zoneDefn.name;
		}		
	}
}
{
	// serializable

	PageDefn.fromDeserializedObject = function(pageDefnAsObject)
	{
		var zoneDefns = [];

		var zoneDefnsAsObjects = pageDefnAsObject.zoneDefns;
		for (var i = 0; i < zoneDefnsAsObjects.length; i++)
		{
			var zoneDefnAsObject = zoneDefnsAsObjects[i];
			var zoneDefn = ZoneDefn.fromDeserializedObject(zoneDefnAsObject);
			zoneDefns.push(zoneDefn);
		}

		var returnValue = new PageDefn(pageDefnAsObject.name, zoneDefns);

		return returnValue;
	}
}

function Zone(defnName)
{
	this.defnName = defnName;
}
{
	Zone.prototype.content = function(document, page)
	{
		if (this._content == null)
		{
			var contentBlock = document.contentBlocks[this.contentBlockName];
			if (contentBlock != null)
			{
				this._content = contentBlock.data;
			}
		}
		
		return this._content;
	}

	Zone.prototype.defn = function(document, page)
	{
		var pageDefn = page.defn(document);
		var returnValue = pageDefn.zoneDefns[this.defnName];
		return returnValue;
	}

	Zone.prototype.update = function(document, page)
	{
		var zoneDefn = this.defn(document, page);

		var content = this.content(document);

		if (content == null)
		{
			return;
		}

		var contentAsLines = [];

		// hack
		var display = new Display(new Coords(0, 0), false);
		display.initialize();

		var fontName = zoneDefn.fontName;
		if (fontName == null)
		{
			fontName = document.fonts[0].name;
		}
		var font = document.fonts[fontName];
		var fontSizeY = font.heightInPixels;
		var charOffset = new Coords(0, 0);

		var lineCurrent = "";
		var wordCurrent = "";

		for (var i = 0; i < content.length; i++)
		{
			var contentChar = content[i];

			wordCurrent += contentChar;

			var widthOfContentChar = display.widthOfText
			(
				contentChar
			);
			charOffset.x += widthOfContentChar;

			if (contentChar == " ")
			{
				lineCurrent += wordCurrent;
				wordCurrent = "";
			}
			else if (contentChar == "\n")
			{
				lineCurrent += wordCurrent + "\n";
				wordCurrent = "";
				charOffset.x = zoneDefn.sizeMinusMargin.x;
			}

			if (charOffset.x >= zoneDefn.sizeMinusMargin.x)
			{
				charOffset.y += fontSizeY;

				if (charOffset.y >= zoneDefn.sizeMinusMargin.y)
				{
					var pageIndex = document.pages.indexOf(page);
					var pageIndexNext = pageIndex + zoneDefn.pageOffsetNext;
					var pageNext = document.pages[pageIndexNext];
					if (pageNext == null)
					{
						break;
					}
					page = pageNext;
					var zoneNextName = zoneDefn.zoneNameNext;
					var zoneNext = pageNext.zones[zoneNextName];
					if (zoneNext != null)
					{
						zoneNext._content = 
							wordCurrent 
							+ content.substr(i + 1);
						wordCurrent = "";
						zoneNext.update(document, page);
						break;
					}
				}

				contentAsLines.push(lineCurrent);
				lineCurrent = "" + wordCurrent;

				charOffset.x = display.widthOfText(wordCurrent);

				wordCurrent = "";
			}
		}

		lineCurrent += wordCurrent;
		contentAsLines.push(lineCurrent);

		this.contentAsLines = contentAsLines;
	}

	// drawable

	Zone.prototype.draw = function(document, page)
	{
		var zone = this;
		var zoneDefn = zone.defn(document, page);

		var display = page.display;
		var drawPos = display.drawPos;

		var zonePos = zoneDefn.pos;
		var zoneSize = zoneDefn.size;
		var zoneMargin = zoneDefn.margin;
		var zoneSizeMinusMargin = zoneDefn.sizeMinusMargin;

		display.drawRectangle(zonePos, zoneSize, "White", "LightGray");

		var contentAsLines = zone.contentAsLines;

		if (contentAsLines != null)
		{	
			var fontName = zoneDefn.fontName;
			if (fontName == null)
			{
				fontName = document.fonts[0].name;
			}
			var font = document.fonts[fontName];
			var fontSizeY = font.heightInPixels;
			display.fontSet(font);

			for (var i = 0; i < contentAsLines.length; i++)
			{
				var contentLine = contentAsLines[i];

				var widthOfWhitespaceBetweenCharacters;

				if (contentLine.indexOf("\n") >= 0)
				{
					widthOfWhitespaceBetweenCharacters = 0;
				}
				else
				{
					contentLine = contentLine.trim();

					var widthOfLineBeforeJustification = display.widthOfText
					(
						contentLine
					);

					var widthOfWhitespaceBetweenCharacters = 
						(
							zoneSizeMinusMargin.x 
							- widthOfLineBeforeJustification
						)
						/ (contentLine.length - 1); 
				}

				contentLine = contentLine.trim();

				var charOffsetX = 0;

				for (var j = 0; j < contentLine.length; j++)
				{
					var contentChar = contentLine[j];			

					drawPos.overwriteWithXY
					(
						zonePos.x + zoneMargin.x + charOffsetX,
						zonePos.y + zoneMargin.y + fontSizeY * (i + 1)
					);

					display.drawText(contentChar, drawPos);

					var widthOfChar = display.widthOfText
					(
						contentChar
					);

					charOffsetX += 
						widthOfChar
						+ widthOfWhitespaceBetweenCharacters;
				}
			}
		}
	}

	// serialzable

	Zone.fromDeserializedObject = function(zoneAsObject)
	{
		var returnValue = new Zone
		(
			zoneAsObject.defnName
		);

		return returnValue;
	}
}

function ZoneDefn(name, pos, size, margin, pageOffsetNext, zoneNameNext, fontName)
{
	this.name = name;
	this.pos = pos;
	this.size = size;
	this.margin = margin;
	this.zoneNameNext = zoneNameNext;
	this.pageOffsetNext = pageOffsetNext;
	this.fontName = fontName;

	this.zoneNamePrev = null;

	this.sizeMinusMargin = this.size.clone().subtract
	(
		this.margin
	).subtract
	(
		this.margin
	);
}
{
	// serialzable

	ZoneDefn.fromDeserializedObject = function(zoneDefnAsObject)
	{
		var returnValue = new ZoneDefn
		(
			zoneDefnAsObject.name, 
			Coords.fromDeserializedObject(zoneDefnAsObject.pos), 
			Coords.fromDeserializedObject(zoneDefnAsObject.size), 
			Coords.fromDeserializedObject(zoneDefnAsObject.margin), 
			zoneDefnAsObject.pageOffsetNext, 
			zoneDefnAsObject.zoneNameNext, 
			zoneDefnAsObject.fontName
		);

		return returnValue;
	}
}

// libraries

// export

function ByteHelper()
{
	// static class
}
{
	ByteHelper.stringUTF8ToBytes = function(stringToConvert)
	{
		var bytes = [];

		for (var i = 0; i < stringToConvert.length; i++)
		{
			var byte = stringToConvert.charCodeAt(i);
			bytes.push(byte);
		} 

		return bytes;	
	}

	ByteHelper.bytesToStringUTF8 = function(bytesToConvert)
	{
		var returnValue = "";

		for (var i = 0; i < bytesToConvert.length; i++)
		{
			var byte = bytesToConvert[i];
			var byteAsChar = String.fromCharCode(byte);
			returnValue += byteAsChar
		}

		return returnValue;
	}
}

function ByteStream(bytes)
{
	this.bytes = bytes;  

	this.byteIndexCurrent = 0;
}
{
	// constants

	ByteStream.BitsPerByte = 8;
	ByteStream.BitsPerByteTimesTwo = ByteStream.BitsPerByte * 2;
	ByteStream.BitsPerByteTimesThree = ByteStream.BitsPerByte * 3;

	// instance methods

	ByteStream.prototype.hasMoreBytes = function()
	{
		return (this.byteIndexCurrent < this.bytes.length);
	}
	
	ByteStream.prototype.readBytes = function(numberOfBytesToRead)
	{
		var returnValue = [];

		for (var b = 0; b < numberOfBytesToRead; b++)
		{
			returnValue[b] = this.readByte();
		}

		return returnValue;
	}

	ByteStream.prototype.readByte = function()
	{
		var returnValue = this.bytes[this.byteIndexCurrent];

		this.byteIndexCurrent++;

		return returnValue;
	}

	ByteStream.prototype.readString = function(lengthOfString)
	{
		var returnValue = "";

		for (var i = 0; i < lengthOfString; i++)
		{
			var byte = this.readByte();

			if (byte != 0)
			{
				var byteAsChar = String.fromCharCode(byte);
				returnValue += byteAsChar;
			}
		}

		return returnValue;
	}

	ByteStream.prototype.writeBytes = function(bytesToWrite)
	{
		for (var b = 0; b < bytesToWrite.length; b++)
		{
			this.bytes.push(bytesToWrite[b]);
		}

		this.byteIndexCurrent = this.bytes.length;
	}

	ByteStream.prototype.writeByte = function(byteToWrite)
	{
		this.bytes.push(byteToWrite);

		this.byteIndexCurrent++;
	}

	ByteStream.prototype.writeString = function(stringToWrite, lengthPadded)
	{	
		for (var i = 0; i < stringToWrite.length; i++)
		{
			var charAsByte = stringToWrite.charCodeAt(i);
			this.writeByte(charAsByte);
		}
		
		var numberOfPaddingChars = lengthPadded - stringToWrite.length;
		for (var i = 0; i < numberOfPaddingChars; i++)
		{
			this.writeByte(0);
		}
	}
}

function FileHelper()
{
	// static class
}
{
    	FileHelper.loadFileAsBytes = function(fileToLoad, callback)
	{   
		var fileReader = new FileReader();
		fileReader.onload = function(fileLoadedEvent)
		{
			var fileLoadedAsBinaryString = 
				fileLoadedEvent.target.result;
			var fileLoadedAsBytes = 
				ByteHelper.stringUTF8ToBytes(fileLoadedAsBinaryString);
			callback(fileToLoad.name, fileLoadedAsBytes);
		}
 
		fileReader.readAsBinaryString(fileToLoad);
	}

	FileHelper.loadFileAsText = function(fileToLoad, callback)
	{
		var fileReader = new FileReader();
		fileReader.onload = function(fileLoadedEvent) 
		{
			var textFromFileLoaded = fileLoadedEvent.target.result;
			callback(fileToLoad.name, textFromFileLoaded);
		};
		fileReader.readAsText(fileToLoad);
	}
 
	FileHelper.saveBytesAsFile = function(bytesToWrite, fileNameToSaveAs)
	{
		var bytesToWriteAsArrayBuffer = new ArrayBuffer(bytesToWrite.length);
		var bytesToWriteAsUIntArray = new Uint8Array(bytesToWriteAsArrayBuffer);
		for (var i = 0; i < bytesToWrite.length; i++) 
		{
			bytesToWriteAsUIntArray[i] = bytesToWrite[i];
		}
 
		var bytesToWriteAsBlob = new Blob
		(
			[ bytesToWriteAsArrayBuffer ], 
			{ type:"application/type" }
		);
 
		var downloadLink = document.createElement("a");
		downloadLink.download = fileNameToSaveAs;
		downloadLink.href = window.URL.createObjectURL(bytesToWriteAsBlob);
		downloadLink.click();
	}

	FileHelper.saveTextAsFile = function(textToSave, fileNameToSaveAs)
	{
		var textToSaveAsBlob = new Blob([textToSave], {type:"text/plain"});
		var textToSaveAsURL = window.URL.createObjectURL(textToSaveAsBlob);

		var downloadLink = document.createElement("a");
		downloadLink.download = fileNameToSaveAs;
		downloadLink.href = textToSaveAsURL;
		downloadLink.click();
	}
}

function TarFile(fileName, entries)
{
	this.fileName = fileName;
	this.entries = entries;
}
{
	// constants

	TarFile.ChunkSize = 512;

	// static methods

	TarFile.fromBytes = function(fileName, bytes)
	{
		var reader = new ByteStream(bytes);

		var entries = [];

		var chunkSize = TarFile.ChunkSize;

		var numberOfConsecutiveZeroChunks = 0;

		while (reader.hasMoreBytes() == true)
		{
			var chunkAsBytes = reader.readBytes(chunkSize);

			var areAllBytesInChunkZeroes = true;

			for (var b = 0; b < chunkAsBytes.length; b++)
			{
				if (chunkAsBytes[b] != 0)
				{
					areAllBytesInChunkZeroes = false;
					break;
				}
			}

			if (areAllBytesInChunkZeroes == true)
			{
				numberOfConsecutiveZeroChunks++;

				if (numberOfConsecutiveZeroChunks == 2)
				{
					break;
				}
			}
			else
			{
				numberOfConsecutiveZeroChunks = 0;

				var entry = TarFileEntry.fromBytes(chunkAsBytes, reader);

				entries.push(entry);
			}
		}

		var returnValue = new TarFile
		(
			fileName,
			entries
		);

		return returnValue;
	}
	
	TarFile.new = function(fileName)
	{
		return new TarFile
		(
			fileName,
			[] // entries
		);
	}

	// instance methods
	
	TarFile.prototype.downloadAs = function(fileNameToSaveAs)
	{	
		FileHelper.saveBytesAsFile
		(
			this.toBytes(),
			fileNameToSaveAs
		)
	}	
	
	TarFile.prototype.entriesForDirectories = function()
	{
		var returnValues = [];
		
		for (var i = 0; i < this.entries.length; i++)
		{
			var entry = this.entries[i];
			if (entry.header.typeFlag.name == "Directory")
			{
				returnValues.push(entry);
			}
		}
		
		return returnValues;
	}
	
	TarFile.prototype.toBytes = function()
	{
		var fileAsBytes = [];		

		// hack - For easier debugging.
		var entriesAsByteArrays = [];
		
		for (var i = 0; i < this.entries.length; i++)
		{
			var entry = this.entries[i];
			var entryAsBytes = entry.toBytes();
			entriesAsByteArrays.push(entryAsBytes);
		}		
		
		for (var i = 0; i < entriesAsByteArrays.length; i++)
		{
			var entryAsBytes = entriesAsByteArrays[i];
			fileAsBytes = fileAsBytes.concat(entryAsBytes);
		}
		
		var chunkSize = TarFile.ChunkSize;
		
		var numberOfZeroChunksToWrite = 2;
		
		for (var i = 0; i < numberOfZeroChunksToWrite; i++)
		{
			for (var b = 0; b < chunkSize; b++)
			{
				fileAsBytes.push(0);
			}
		}

		return fileAsBytes;
	}
	
	// strings

	TarFile.prototype.toString = function()
	{
		var newline = "\n";

		var returnValue = "[TarFile]" + newline;

		for (var i = 0; i < this.entries.length; i++)
		{
			var entry = this.entries[i];
			var entryAsString = entry.toString();
			returnValue += entryAsString;
		}

		returnValue += "[/TarFile]" + newline;

		return returnValue;
	}
}

function TarFileEntry(header, dataAsBytes)
{
	this.header = header;
	this.dataAsBytes = dataAsBytes;
}
{
	// methods
	
	// static methods
	
	TarFileEntry.directoryNew = function(directoryName)
	{
		var header = new TarFileEntryHeader.directoryNew(directoryName);
		
		var entry = new TarFileEntry(header, []);
		
		return entry;
	}
	
	TarFileEntry.fileNew = function(fileName, fileContentsAsBytes)
	{
		var header = new TarFileEntryHeader.fileNew(fileName, fileContentsAsBytes);
		
		var entry = new TarFileEntry(header, fileContentsAsBytes);
		
		return entry;
	}
	
	TarFileEntry.fromBytes = function(chunkAsBytes, reader)
	{
		var chunkSize = TarFile.ChunkSize;
	
		var header = TarFileEntryHeader.fromBytes
		(
			chunkAsBytes
		);
	
		var sizeOfDataEntryInBytesUnpadded = header.fileSizeInBytes;	

		var numberOfChunksOccupiedByDataEntry = Math.ceil
		(
			sizeOfDataEntryInBytesUnpadded / chunkSize
		)
	
		var sizeOfDataEntryInBytesPadded = 
			numberOfChunksOccupiedByDataEntry
			* chunkSize;
	
		var dataAsBytes = reader.readBytes
		(
			sizeOfDataEntryInBytesPadded
		).slice
		(
			0, sizeOfDataEntryInBytesUnpadded
		);
	
		var entry = new TarFileEntry(header, dataAsBytes);
		
		return entry;
	}
	
	TarFileEntry.manyFromByteArrays = function
	(
		fileNamePrefix, fileNameSuffix, entriesAsByteArrays
	)
	{
		var returnValues = [];
		
		for (var i = 0; i < entriesAsByteArrays.length; i++)
		{
			var entryAsBytes = entriesAsByteArrays[i];
			var entry = TarFileEntry.fileNew
			(		
				fileNamePrefix + i + fileNameSuffix,
				entryAsBytes
			);
			
			returnValues.push(entry);
		}
		
		return returnValues;
	}
	
	// instance methods

	TarFileEntry.prototype.download = function(event)
	{
		FileHelper.saveBytesAsFile
		(
			this.dataAsBytes,
			this.header.fileName
		);
	}
	
	TarFileEntry.prototype.remove = function(event)
	{
		alert("Not yet implemented!"); // todo
	}
	
	TarFileEntry.prototype.toBytes = function()
	{
		var entryAsBytes = [];
	
		var chunkSize = TarFile.ChunkSize;
	
		var headerAsBytes = this.header.toBytes();
		entryAsBytes = entryAsBytes.concat(headerAsBytes);
		
		entryAsBytes = entryAsBytes.concat(this.dataAsBytes);

		var sizeOfDataEntryInBytesUnpadded = this.header.fileSizeInBytes;	

		var numberOfChunksOccupiedByDataEntry = Math.ceil
		(
			sizeOfDataEntryInBytesUnpadded / chunkSize
		)
	
		var sizeOfDataEntryInBytesPadded = 
			numberOfChunksOccupiedByDataEntry
			* chunkSize;
			
		var numberOfBytesOfPadding = 
			sizeOfDataEntryInBytesPadded - sizeOfDataEntryInBytesUnpadded;
	
		for (var i = 0; i < numberOfBytesOfPadding; i++)
		{
			entryAsBytes.push(0);
		}
		
		return entryAsBytes;
	}	
		
	// strings
	
	TarFileEntry.prototype.toString = function()
	{
		var newline = "\n";

		headerAsString = this.header.toString();

		var dataAsHexadecimalString = ByteHelper.bytesToStringHexadecimal
		(
			this.dataAsBytes
		);

		var returnValue = 
			"[TarFileEntry]" + newline
			+ headerAsString
			+ "[Data]"
			+ dataAsHexadecimalString
			+ "[/Data]" + newline
			+ "[/TarFileEntry]"
			+ newline;

		return returnValue
	}
	
}

function TarFileEntryHeader
(
	fileName,
	fileMode,
	userIDOfOwner,
	userIDOfGroup,
	fileSizeInBytes,
	timeModifiedInUnixFormat,
	checksum,
	typeFlag,
	nameOfLinkedFile,
	uStarIndicator,
	uStarVersion,
	userNameOfOwner,
	groupNameOfOwner,
	deviceNumberMajor,
	deviceNumberMinor,
	filenamePrefix
)
{
	this.fileName = fileName;
	this.fileMode = fileMode;
	this.userIDOfOwner = userIDOfOwner;
	this.userIDOfGroup = userIDOfGroup;
	this.fileSizeInBytes = fileSizeInBytes;
	this.timeModifiedInUnixFormat = timeModifiedInUnixFormat;
	this.checksum = checksum;
	this.typeFlag = typeFlag;
	this.nameOfLinkedFile = nameOfLinkedFile;
	this.uStarIndicator = uStarIndicator;
	this.uStarVersion = uStarVersion;
	this.userNameOfOwner = userNameOfOwner;
	this.groupNameOfOwner = groupNameOfOwner;
	this.deviceNumberMajor = deviceNumberMajor;
	this.deviceNumberMinor = deviceNumberMinor;
	this.filenamePrefix = filenamePrefix;
}
{
	TarFileEntryHeader.SizeInBytes = 500;

	// static methods
	
	TarFileEntryHeader.default = function()
	{
		var now = new Date();
		var unixEpoch = new Date(1970, 1, 1);
		var millisecondsSinceUnixEpoch = now - unixEpoch;
		var secondsSinceUnixEpoch = Math.floor
		(
			millisecondsSinceUnixEpoch / 1000
		);
		var secondsSinceUnixEpochAsStringOctal = 
			secondsSinceUnixEpoch.toString(8).padRight(12, " ");
		var timeModifiedInUnixFormat = []; 
		for (var i = 0; i < secondsSinceUnixEpochAsStringOctal.length; i++)
		{
			var digitAsASCIICode = 
				secondsSinceUnixEpochAsStringOctal.charCodeAt(i);
			timeModifiedInUnixFormat.push(digitAsASCIICode);
		}

		var returnValue = new TarFileEntryHeader
		(
			"".padRight(100, "\0"), // fileName
			"100777 \0", // fileMode
			"0 \0".padLeft(8, " "), // userIDOfOwner
			"0 \0".padLeft(8, " "), // userIDOfGroup
			0, // fileSizeInBytes
			timeModifiedInUnixFormat,
			0, // checksum
			TarFileTypeFlag.Instances.Normal,		
			"".padRight(100, "\0"), // nameOfLinkedFile,
			"".padRight(6, "\0"), // uStarIndicator,
			"".padRight(2, "\0"), // uStarVersion,
			"".padRight(32, "\0"), // userNameOfOwner,
			"".padRight(32, "\0"), // groupNameOfOwner,
			"".padRight(8, "\0"), // deviceNumberMajor,
			"".padRight(8, "\0"), // deviceNumberMinor,
			"".padRight(155, "\0") // filenamePrefix	
		);		
		
		return returnValue;
	}
	
	TarFileEntryHeader.directoryNew = function(directoryName)
	{
		var header = TarFileEntryHeader.default();
		header.fileName = directoryName;
		header.typeFlag = TarFileTypeFlag.Instances.Directory;
		header.fileSizeInBytes = 0;
		header.checksumCalculate();
		
		return header;
	}
	
	TarFileEntryHeader.fileNew = function(fileName, fileContentsAsBytes)
	{
		var header = TarFileEntryHeader.default();
		header.fileName = fileName;
		header.typeFlag = TarFileTypeFlag.Instances.Normal;
		header.fileSizeInBytes = fileContentsAsBytes.length;
		header.checksumCalculate();
		
		return header;
	}

	TarFileEntryHeader.fromBytes = function(bytes)
	{
		var reader = new ByteStream(bytes);

		var fileName = reader.readString(100).trim();
		var fileMode = reader.readString(8);
		var userIDOfOwner = reader.readString(8);
		var userIDOfGroup = reader.readString(8);
		var fileSizeInBytesAsStringOctal = reader.readString(12);
		var timeModifiedInUnixFormat = reader.readBytes(12);
		var checksumAsStringOctal = reader.readString(8);
		var typeFlagValue = reader.readString(1);
		var nameOfLinkedFile = reader.readString(100);
		var uStarIndicator = reader.readString(6);
		var uStarVersion = reader.readString(2);
		var userNameOfOwner = reader.readString(32);
		var groupNameOfOwner = reader.readString(32);
		var deviceNumberMajor = reader.readString(8);
		var deviceNumberMinor = reader.readString(8);
		var filenamePrefix = reader.readString(155);
		var reserved = reader.readBytes(12);

		var fileSizeInBytes = parseInt
		(
			fileSizeInBytesAsStringOctal.trim(), 8
		);
		
		var checksum = parseInt
		(
			checksumAsStringOctal, 8
		);		
		
		var typeFlags = TarFileTypeFlag.Instances._All;
		var typeFlagID = "_" + typeFlagValue;
		var typeFlag = typeFlags[typeFlagID];

		var returnValue = new TarFileEntryHeader
		(
			fileName,
			fileMode,
			userIDOfOwner,
			userIDOfGroup,
			fileSizeInBytes,
			timeModifiedInUnixFormat,
			checksum,
			typeFlag,
			nameOfLinkedFile,
			uStarIndicator,
			uStarVersion,
			userNameOfOwner,
			groupNameOfOwner,
			deviceNumberMajor,
			deviceNumberMinor,
			filenamePrefix
		);

		return returnValue;
	}

	// instance methods
	
	TarFileEntryHeader.prototype.checksumCalculate = function()
	{	
		var thisAsBytes = this.toBytes();
	
		// The checksum is the sum of all bytes in the header,
		// except we obviously can't include the checksum itself.
		// So it's assumed that all 8 of checksum's bytes are spaces (0x20=32).
		// So we need to set this manually.
						
		var offsetOfChecksumInBytes = 148;
		var numberOfBytesInChecksum = 8;
		var presumedValueOfEachChecksumByte = " ".charCodeAt(0);
		for (var i = 0; i < numberOfBytesInChecksum; i++)
		{
			var offsetOfByte = offsetOfChecksumInBytes + i;
			thisAsBytes[offsetOfByte] = presumedValueOfEachChecksumByte;
		}
		
		var checksumSoFar = 0;

		for (var i = 0; i < thisAsBytes.length; i++)
		{
			var byteToAdd = thisAsBytes[i];
			checksumSoFar += byteToAdd;
		}		

		this.checksum = checksumSoFar;
		
		return this.checksum;
	}
	
	TarFileEntryHeader.prototype.toBytes = function()
	{
		var headerAsBytes = [];
		var writer = new ByteStream(headerAsBytes);
		
		var fileSizeInBytesAsStringOctal = (this.fileSizeInBytes.toString(8) + " ").padLeft(12, " ")
		var checksumAsStringOctal = (this.checksum.toString(8) + " \0").padLeft(8, " ");

		writer.writeString(this.fileName, 100);
		writer.writeString(this.fileMode, 8);
		writer.writeString(this.userIDOfOwner, 8);
		writer.writeString(this.userIDOfGroup, 8);
		writer.writeString(fileSizeInBytesAsStringOctal, 12);
		writer.writeBytes(this.timeModifiedInUnixFormat);
		writer.writeString(checksumAsStringOctal, 8);
		writer.writeString(this.typeFlag.value, 1);		
		writer.writeString(this.nameOfLinkedFile, 100);
		writer.writeString(this.uStarIndicator, 6);
		writer.writeString(this.uStarVersion, 2);
		writer.writeString(this.userNameOfOwner, 32);
		writer.writeString(this.groupNameOfOwner, 32);
		writer.writeString(this.deviceNumberMajor, 8);
		writer.writeString(this.deviceNumberMinor, 8);
		writer.writeString(this.filenamePrefix, 155);
		writer.writeString("".padRight(12, "\0")); // reserved

		return headerAsBytes;
	}		
		
	// strings

	TarFileEntryHeader.prototype.toString = function()
	{		
		var newline = "\n";
	
		var returnValue = 
			"[TarFileEntryHeader "
			+ "fileName='" + this.fileName + "' "
			+ "typeFlag='" + (this.typeFlag == null ? "err" : this.typeFlag.name) + "' "
			+ "fileSizeInBytes='" + this.fileSizeInBytes + "' "
			+ "]"
			+ newline;

		return returnValue;
	}
}	

function TarFileTypeFlag(value, name)
{
	this.value = value;
	this.id = "_" + this.value;
	this.name = name;
}
{
	TarFileTypeFlag.Instances = new TarFileTypeFlag_Instances();

	function TarFileTypeFlag_Instances()
	{
		this.Normal 		= new TarFileTypeFlag("0", "Normal");
		this.HardLink 		= new TarFileTypeFlag("1", "Hard Link");
		this.SymbolicLink 	= new TarFileTypeFlag("2", "Symbolic Link");
		this.CharacterSpecial 	= new TarFileTypeFlag("3", "Character Special");
		this.BlockSpecial 	= new TarFileTypeFlag("4", "Block Special");
		this.Directory		= new TarFileTypeFlag("5", "Directory");
		this.FIFO		= new TarFileTypeFlag("6", "FIFO");
		this.ContiguousFile 	= new TarFileTypeFlag("7", "Contiguous File");

		// Additional types not implemented:
		// 'g' - global extended header with meta data (POSIX.1-2001)
		// 'x' - extended header with meta data for the next file in the archive (POSIX.1-2001)
		// 'A'–'Z' - Vendor specific extensions (POSIX.1-1988)
		// [other values] - reserved for future standardization

		this._All = 
		[
			this.Normal,
			this.HardLink,
			this.SymbolicLink,
			this.CharacterSpecial,
			this.BlockSpecial,
			this.Directory,
			this.FIFO,
			this.ContiguousFile,
		];

		for (var i = 0; i < this._All.length; i++)
		{
			var item = this._All[i];
			this._All[item.id] = item;
		}
	}
}

</script>
</body>
</html>

Posted in Uncategorized | Tagged , , , | Leave a comment

Demonstrating the RSA Algorithm in JavaScript

The JavaScript code below picks two random two-digit primes, uses them to generate a RSA keypair, then uses that keypair to encrypt and decrypt a simple message. It uses the LargeInteger class introduced in a previous post to handle the very large numbers involved in the RSA encryption process. To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

RSA is an asymmetric encryption algorithm developed in the late 1970’s by the researchers Ron Rivest, Adi Shamir, and Leonard Adleman. It works by the process described below.

1. Choose two (ideally very large) prime numbers at random. Call these numbers p and q.

2. Multiply p and q together to find the modulus.

3. Find the least common multiple of (p – 1) and (q – 1). Call this value the totient.

4. Choose a random number greater than 2 and less than the totient. Call this the public exponent candidate.

5. Verify that the public exponent candidate and the totient are co-prime, that is to say, that they have no common factors other than 1. If they are not co-prime, return to step 4 and choose another candidate. If they are co-prime, accept the candidate as the public exponent.

6. Find the modular multiplicative inverse of the public exponent with respect to the modulus, by way of an algorithm too complicated to describe here. This value is the private key.

7. To encrypt a message, first encode it as a number or a series of numbers (each less than the modulus?), raise each number to the public exponent, and “modulo” it against the modulus (that is, divide it by the modulus and take the remainder). This is the encrypted value.

8. To decrypt an encrypted value, raise it to the private exponent and modulo it against the modulus again. The result should be the original, unecrypted value.

This program is for demonstration purposes only, and should be no means be depended on to secure anything in the real world. Aside from any other number of known and unknown vulnerabilities, an RSA keypair that uses two-digit primes obviously can’t possibly be very secure, but that’s all this implementation can handle due to the inefficiency of its various mathematical calculations.

RSAEncryption.png


<html>
<body>
<script type="text/javascript">

// main

function main()
{
	var newline = "<br />";

	// This implementation can't handle big numbers.
	var digitsPerPrime = 2; 

	var keyPair = new EncryptionKeyPair().generate(digitsPerPrime);
	document.write("Key pair is " + keyPair.toString() + newline);

	// hack
	// We're assuming the modulus is greater than the messageToEncrypt.
	// I believe this may cause problems on the rare occasions 
	// when the modulus ends up being less than the message value.

	var messageToEncryptAsInt = 42;
	var base = keyPair.modulus.base;
	var messageToEncrypt = new LargeInteger(base).setFromInt(messageToEncryptAsInt);
	document.write("Message to encrypt is " + messageToEncrypt.toString() + newline);
	
	var messageEncrypted = keyPair.encrypt(messageToEncrypt);
	document.write("Message encrypted is " + messageEncrypted.toString() + newline);

	var messageDecrypted = keyPair.decrypt(messageEncrypted);
	document.write("Message decrypted is " + messageDecrypted.toString() + newline);
}

// classes

function EncryptionKeyPair(modulus, publicExponent, privateExponent)
{
	this.modulus = modulus;
	this.publicExponent = publicExponent;
	this.privateExponent = privateExponent;
}
{
	EncryptionKeyPair.prototype.decrypt = function(messageToDecrypt)
	{
		return this.encryptOrDecrypt(messageToDecrypt, this.publicExponent);	
	}

	EncryptionKeyPair.prototype.encrypt = function(messageToEncrypt)
	{
		return this.encryptOrDecrypt(messageToEncrypt, this.privateExponent);	
	}

	EncryptionKeyPair.prototype.encryptOrDecrypt = function(message, exponent)
	{
		var result = message.raiseToPower
		(
			exponent
		).modulo
		(
			this.modulus
		);

		return message;
	}

	EncryptionKeyPair.prototype.generate = function(digitsPerPrime)
	{
		// Adapted from an example found at the URL
		// https://en.wikipedia.org/wiki/RSA_(cryptosystem)

		var primesRandom = [];
		var base = 10;
		var valueMaxForNumberOfDigits = 
			new LargeInteger(base).setFromInt(base).raiseToPower
			(
				new LargeInteger(base).setFromInt(digitsPerPrime)
			);

		var numberOfPrimesToChoose = 2;

		for (var i = 0; i < numberOfPrimesToChoose; i++)
		{
			var primeCandidate = 
				valueMaxForNumberOfDigits.clone().randomize();

			while (MathHelperLargeInteger.isPrime(primeCandidate) == false)
			{
				primeCandidate.increment();
			}

			primesRandom.push(primeCandidate);
		}
				
		var prime0 = primesRandom[0];
		var prime1 = primesRandom[1];

		var modulus = prime0.clone().multiply(prime1);

		var totient = MathHelperLargeInteger.leastCommonMultiple
		(
			prime0.clone().decrement(), 
			prime1.clone().decrement()
		);

		var publicExponentCandidate = totient.clone().randomize();

		var areCoprime = MathHelperLargeInteger.areCoprime;

		while (areCoprime(publicExponentCandidate, totient) == false)
		{
			publicExponentCandidate.increment();
			if (publicExponentCandidate.isGreaterThanOrEqualTo(totient))
			{
				publicExponentCandidate.setFromInt(2);
			}
		}

		var publicExponent = publicExponentCandidate;

		var privateExponent = MathHelperLargeInteger.modularMultiplicativeInverse
		(
			publicExponent,
			totient
		);
		
		this.modulus = modulus;
		this.publicExponent = publicExponent;
		this.privateExponent = privateExponent;

		return this;
	}

	// string 

	EncryptionKeyPair.prototype.toString = function()
	{
		var objectToSerialize = 
		{
			"modulus" : this.modulus.toString(),
			"publicExponent" : this.publicExponent.toString(),
			"privateExponent" : this.privateExponent.toString()

		}
		var returnValue = JSON.stringify(objectToSerialize);
		return returnValue;
	}
}

function LargeInteger(base)
{
	this.base = base;
	this.digits = [];
}
{
	// instance methods

	LargeInteger.prototype.add = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsGreater;

		if (numberOfDigitsInThis >= numberOfDigitsInOther)
		{
			numberOfDigitsGreater = numberOfDigitsInThis;
		}
		else
		{
			numberOfDigitsGreater = numberOfDigitsInOther;
		}

		var numberOfDigitsInSum = numberOfDigitsGreater + 1;

		this.expandNumberOfDigitsTo(numberOfDigitsInSum);
		other.expandNumberOfDigitsTo(numberOfDigitsInSum);

		var carryDigit = 0;

		for (var i = 0; i < numberOfDigitsInSum; i++)
		{
			var sumAtDigit = this.digits[i] + other.digits[i] + carryDigit;

			var digitValue = sumAtDigit % this.base;
			carryDigit = (sumAtDigit - digitValue) / this.base;

			this.digits[i] = digitValue;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.clone = function()
	{
		var returnValue = new LargeInteger(this.base);

		returnValue.overwriteWith(this);

		return returnValue;
	}

	LargeInteger.prototype.decrement = function()
	{
		return this.subtract(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.divide = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();
		var base = dividend.base;

		var one = new LargeInteger(base).setFromInt(1);

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		dividend.multiplyByBaseRaisedTo(lengthOfDivisorInDigits);
		divisor.multiplyByBaseRaisedTo(differenceInLengths + lengthOfDivisorInDigits);

		var result = new LargeInteger(base).setFromInt(0);

		while (divisor.digits.length > 0)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
				result.add(one);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
				result.multiplyByBaseRaisedTo(1);
			}	
		}

		result.divideByBaseRaisedTo(2 * lengthOfDivisorInDigits);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.divideByBaseRaisedTo = function(exponent)
	{
		this.digits.splice(0, exponent);

		return this;
	}

	LargeInteger.prototype.expandNumberOfDigitsTo = function(numberOfDigitsTotal)
	{
		var numberOfDigitsToAdd = numberOfDigitsTotal - this.digits.length;
		for (var i = 0; i < numberOfDigitsToAdd; i++)
		{
			this.digits.push(0);	
		}

		return this;
	}

	LargeInteger.prototype.increment = function()
	{
		return this.add(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.isEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis != numberOfDigitsInOther)
		{
			returnValue = false;
		}
		else
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis != digitOther)
				{
					returnValue = false;
					break;
				}
			}
		}

		return returnValue;
	}

	LargeInteger.prototype.isGreaterThan = function(other)
	{
		var returnValue = (this.isLessThanOrEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.isGreaterThanOrEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis > numberOfDigitsInOther)
		{
			returnValue = true;
		}
		else if (numberOfDigitsInThis == numberOfDigitsInOther)
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis < digitOther)
				{
					returnValue = false;
					break;
				}
				else if (digitThis > digitOther)
				{
					break;
				}			
			}
		}
		else
		{
			returnValue = false;
		}

		return returnValue;
	}

	LargeInteger.prototype.isLessThan = function(other)
	{
		var returnValue = (this.isGreaterThanOrEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.isLessThanOrEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis < numberOfDigitsInOther)
		{
			returnValue = true;
		}
		else if (numberOfDigitsInThis == numberOfDigitsInOther)
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis > digitOther)
				{
					returnValue = false;
					break;
				}
				else if (digitThis < digitOther)
				{
					break;
				}			
			}
		}
		else
		{
			returnValue = false;
		}

		return returnValue;
	}

	LargeInteger.prototype.isNotEqualTo = function(other)
	{
		var returnValue = (this.isEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.modulo = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		var divisorOriginal = divisor.clone();
		divisor.multiplyByBaseRaisedTo(differenceInLengths);

		while (divisor.digits.length >= lengthOfDivisorInDigits)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
			}	
		}

		this.overwriteWith(dividend);

		return this;
	}

	LargeInteger.prototype.multiply = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;		

		var numberOfDigitsInProduct = numberOfDigitsInThis + numberOfDigitsInOther; 
		var product = new LargeInteger(this.base).expandNumberOfDigitsTo(numberOfDigitsInProduct);

		for (var i = 0; i < numberOfDigitsInThis; i++)
		{
			var digitFromThis = this.digits[i];

			for (var j = 0; j < numberOfDigitsInOther; j++)
			{
				var digitFromOther = other.digits[j];

				var productOfDigits = 
					digitFromThis 
					* digitFromOther;

				var productDigitIndex = i + j;

				var carryDigit = productOfDigits; 

				while (carryDigit > 0)
				{
					var sumAtDigit = product.digits[productDigitIndex] + carryDigit;

					var digitValue = sumAtDigit % this.base;
					carryDigit = (sumAtDigit - digitValue) / this.base;

					product.digits[productDigitIndex] = digitValue;

					productDigitIndex++;
				}
			}
		}

		product.removeLeadingZeroes();
		this.overwriteWith(product);

		return this;
	}

	LargeInteger.prototype.multiplyByBaseRaisedTo = function(exponent)
	{
		for (var i = 0; i < exponent; i++)
		{
			this.digits.splice(0, 0, 0);
		}

		return this;
	}

	LargeInteger.prototype.overwriteWith = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			this.digits[i] = other.digits[i];
		}

		if (numberOfDigitsInThis > numberOfDigitsInOther)
		{
			this.digits.splice
			(
				numberOfDigitsInOther, 
				numberOfDigitsInThis - numberOfDigitsInOther
			);
		}		

		return this;
	}

	LargeInteger.prototype.randomize = function()
	{
		var valueOriginal = this.clone();
		var base = new LargeInteger(this.base).setFromInt(this.base);
		var numberOfDigits = new LargeInteger(this.base).setFromInt(this.digits.length);		
		var valueMaxForNumberOfDigits = base.raiseToPower(numberOfDigits);

		for (var i = 0; i < this.digits.length; i++)
		{
			digitRandom = Math.floor
			(
				Math.random() * this.base
			);

			this.digits[i] = digitRandom;
		}

		this.multiply(valueOriginal).divide(valueMaxForNumberOfDigits);

		return this;
	}

	LargeInteger.prototype.raiseToPower = function(exponent)
	{
		var result = this.raiseToPowerBySquaring(exponent);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.raiseToPowerBySquaring = function(exponent)
	{
		var returnValue = LargeInteger.raiseValueToPowerBySquaring
		(
			this.clone(), 
			exponent.clone(), 
			new LargeInteger(this.base).setFromInt(1),
			new LargeInteger(this.base).setFromInt(2)
		);

		return returnValue;
	}

	LargeInteger.raiseValueToPowerBySquaring = function
	(
		valueToRaise, exponent, constantOne, constantTwo
	)
	{
		var returnValue;

		if (exponent.digits.length == 1 && exponent.digits[0] == 1)
		{
			returnValue = valueToRaise;
		}
		else if (exponent.digits[0] % 2 == 0)
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().divide(constantTwo),
				constantOne,
				constantTwo
			);
		}
		else
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().subtract(constantOne).divide(constantTwo),
				constantOne,
				constantTwo
			).multiply
			(
				valueToRaise
			);
		}

		return returnValue;
	}

	LargeInteger.prototype.removeLeadingZeroes = function()
	{
		return this.removeLeadingZeroesDownTo(0);
	}

	LargeInteger.prototype.removeLeadingZeroesDownTo = function(numberOfDigitsTotal)
	{
		var i = this.digits.length - 1;

		while (i >= numberOfDigitsTotal && this.digits[i] == 0)
		{
			this.digits.splice(i, 1);	
			i--;
		}

		return this;
	}

	LargeInteger.prototype.setFromInt = function(valueToSet)
	{
		var d = 0;

		while (valueToSet > 0)
		{
			var digitValue = valueToSet % this.base;
			valueToSet = (valueToSet - digitValue) / this.base;
			this.digits[d] = digitValue;

			d++;
		}

		this.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.setToOne = function()
	{
		this.digits = [1];
		return this;
	}

	LargeInteger.prototype.setToZero = function()
	{
		this.digits = [];
		return this;
	}

	LargeInteger.prototype.subtract = function(other)
	{
		var base = this.base;

		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsInThis = this.digits.length;
		other.expandNumberOfDigitsTo(numberOfDigitsInThis);

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			var digitFromThis = this.digits[i];
			var digitFromOther = other.digits[i];

			if (digitFromThis < digitFromOther)
			{
				var valueBorrowed = 0;
				var j = i;

				while (valueBorrowed == 0)
				{
					j++;

					var digitToBorrowFrom = this.digits[j];
					if (digitToBorrowFrom > 0)
					{
						valueBorrowed = base;
						this.digits[j]--;

						j--;
						while (j > i)
						{
							this.digits[j] = base - 1;
							j--;
						}
					}
				}

				digitFromThis += valueBorrowed;				
			}

			this.digits[i] = digitFromThis - digitFromOther;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.toInt = function()
	{
		var returnValue = 0;

		var placeMultiplierCurrent = 1;

		var numberOfDigits = this.digits.length;

		for (var i = 0; i < numberOfDigits; i++)
		{
			returnValue += this.digits[i] * placeMultiplierCurrent;

			placeMultiplierCurrent *= this.base;
		}

		return returnValue;
	}


	LargeInteger.prototype.toString = function()
	{
		var returnValue = "";

		var numberOfDigits = this.digits.length;

		for (var i = numberOfDigits - 1; i >= 0; i--)
		{
			returnValue += "" + this.digits[i];
		}

		return returnValue;
	}
}

function MathHelperLargeInteger()
{
	// static class
}
{
	MathHelperLargeInteger.areCoprime = function(a, b)
	{
		var greatestCommonDivisor = MathHelperLargeInteger.greatestCommonDivisor(a, b);
		var one = new LargeInteger(a.base).setToOne();
		var returnValue = greatestCommonDivisor.isEqualTo(one);
		return returnValue;
	}

	MathHelperLargeInteger.greatestCommonDivisor = function(a, b)
	{
		// Adapted from pseudocode at the URL:
		// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

		var base = a.base;

		var s = new LargeInteger(base).setToZero();    
		var old_s = new LargeInteger(base).setToOne();

		var t = new LargeInteger(base).setToOne();   
		var old_t = new LargeInteger(base).setToZero();

		var r = b.clone();
		var old_r = a.clone();

		var quotient = new LargeInteger(base);
		var temp = new LargeInteger(base);
		var temp2 = new LargeInteger(base);
		var zero = new LargeInteger(base).setToZero();
		
		while (r.isNotEqualTo(zero))
		{
			quotient.overwriteWith(old_r).divide(r);

			temp.overwriteWith(r);
			r.overwriteWith(old_r).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_r.overwriteWith(temp);

			temp.overwriteWith(s);
			s.overwriteWith(old_s).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_s.overwriteWith(temp);

			temp.overwriteWith(t);
			t.overwriteWith(old_t).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_t.overwriteWith(temp);
		}

		var returnValue = old_r;
	
		return returnValue;
	}

	MathHelperLargeInteger.isPrime = function(possiblePrime, two, zero, temp)
	{
		// hack - This is almost certainly not the most efficient algorithm.

		var returnValue = true;

		if (two == null)
		{
			var base = possiblePrime.base;
			two = new LargeInteger(base).setFromInt(2);
			zero = new LargeInteger(base).setToZero();
			temp = new LargeInteger(base);
		}
		
		if (possiblePrime.isLessThan(two))
		{
			returnValue = false;	
		}
		else
		{
			// hack - A lot of re-instancing here.
			var possiblePrimeHalf = possiblePrime.clone().divide(two);
			var factorCurrent = two.clone();

			while (factorCurrent.isLessThanOrEqualTo(possiblePrimeHalf))
			{
				while (MathHelperLargeInteger.isPrime(factorCurrent, two, zero, temp) == false)
				{
					factorCurrent.increment();
				}

				var isPossiblePrimeAMultipleOfCurrentDivisor = 
					temp.overwriteWith
					(
						possiblePrime
					).modulo
					(
						factorCurrent
					).isEqualTo
					(
						zero
					);
	
				if (isPossiblePrimeAMultipleOfCurrentDivisor == true)
				{
					returnValue = false;
					break;
				}

				factorCurrent.increment();
			}
		}

		return returnValue;
	}

	MathHelperLargeInteger.leastCommonMultiple = function(a, b)
	{
		var product = a.clone().multiply(b);
		var greatestCommonDivisor = MathHelperLargeInteger.greatestCommonDivisor(a, b);
		var returnValue = product.divide(greatestCommonDivisor);
		return returnValue;
	}

	MathHelperLargeInteger.modularMultiplicativeInverse = function(valueToInvert, modulus)
	{
		// Adapted from:
		// https://math.stackexchange.com/questions/67171/
		// calculating-the-modular-multiplicative-inverse-without-all-those-strange-looking

		var returnValue;

		var base = valueToInvert.base;

		var one = new LargeInteger(base).setToOne();

		if (valueToInvert.isEqualTo(one)) 
		{
			returnValue = one.clone();	
		}
		else
		{
			var temp = new LargeInteger(base);
			var temp2 = new LargeInteger(base);

			var c = modulus.clone().modulo(valueToInvert);
			var d = valueToInvert.clone();
			var u = modulus.clone().divide(valueToInvert);
			var v = one.clone();

			while (c.isNotEqualTo(one) && d.isNotEqualTo(one)) 
			{
				v.add
				(
					temp.overwriteWith
					(
						d
					).divide
					(
						c
					).multiply
					(
						u
					)
				);

				d.modulo(c);

				if (d.isNotEqualTo(one)) 
				{
					u.add
					(
						temp.overwriteWith
						(
							c
						).divide
						(
							d
						).multiply
						(
							v
						)
					);

					c.modulo(d);
				}
			}

			var tAsInt = (d.isNotEqualTo(one) ? 1 : 0);
			var t = new LargeInteger(base).setFromInt(tAsInt);

			returnValue = v.multiply
			(
				temp.overwriteWith
				(
					one
				).subtract
				(
					t
				)
			).add
			(
				temp.overwriteWith(t).multiply
				(
					temp2.overwriteWith
					(
						modulus
					).subtract
					(
						u
					)
				)
			);
		}

		return returnValue;
	}

}

// run

main();

</script>
</body>
</html>

Posted in Uncategorized | Tagged , , , , , | Leave a comment