Steve is currently developing intelligent pattern-recognition systems for manufacturing as a senior principal engineer for the Boeing Commercial Airplane Group. He can be contacted at stevew@eskimo.com.
One of the major plot elements of the film Rising Sun hinged on sophisticated digital imagery of a murder, recorded by security cameras. To cover up the guilt of a political figure, the face of the perpetrator was digitally replaced with that of another person. Sean Connery and friends eventually triumph by doing a little bit-twiddling to prove that the image had been manipulated, thus leading back toward the truth.
In reality, a similar digital rework would be incredibly clumsy. A modern digital warrior can make such modifications nearly undetectable, as we saw with the disabled Vietnam vet in the movie Forrest Gump.
Films are (mostly) intentionally fictitious. Everybody applauds the genius of the folks at Industrial Light and Magic and other such special-effects teams because we can finally hold our imaginations right up there beside reality and ask, "Why not?"
But what if those images contained key legal evidence in a murder trial or journalist's photographs of foreign atrocities? Conceivably, we could cheer on a war based on evidence hacked up in a computer system.
This is a serious problem.
Ironically, even as our prehistoric contract with these visual channels of truth is being rewritten, an old, old method may come to our rescue.
In the middle ages, kings, dukes, barons, and anyone else who styled themselves important would carve a design onto a stamp or a ring. This was used to impress a wax or lead closure sealing the wrappings of items sent by courier, ostensibly proving that the document or package did indeed come from them and hence could be considered authentic.
In time, the stamp took the name of its function and became known as a "seal." Figure 1 shows King John's seal, which he affixed to the Magna Carta to represent his word of honor. By this act, a government acknowledged for the first time its relationship with the rights and responsibilities of the people.
When literacy became more widespread and it became common for people to have more than one name, the written signature replaced the seal on most legal documents and other important works.
If we are going to continue to trust images as evidence of true events, I propose that we use that old digital magic to revive the original concept of the royal seal, and apply it to the data streams that feed us truths. The method should be easy, ubiquitous, difficult or impossible to defeat, and fast.
In this article, I outline a class of simple algorithms that satisfy most, if not all of those requirements, and which can be implemented by anyone with access to a computer language. I believe it has advantages in storage, speed, and stealthiness over systems like those found in RSA Data Security's RSAREF cryptography toolkit (specifically, MD2 and MD5). In addition to the C source code for the algorithms presented here, executables and two test Targa images are available electronically; see "Availability," page 3. Note that the code is slower than it could be because it was written to illustrate algorithms, and not built for speed.
In the simplest and most common format, digital images are represented by rectangular arrays of picture elements (pixels), each of which may or may not be physically square. The common VGA display has 480 rows of 640 pixels each, for instance.
The numbers representing a single pixel, used to reconstruct its color and intensity, come in assorted flavors. In direct representational models, they are just brightness, either of a gray-level or a tri-stimulus component of a color model.
The simplest model for direct image representation is 8-bit monochrome. Each pixel is one byte deep and can thus display 256 levels of brightness. A properly scaled image will use this fairly narrow dynamic range to represent levels from black to white. A poorly scaled image will be illegibly washed out in shades of gray. Figure 2 illustrates the logical structure of an 8-bit monochrome image.
It's more interesting when you attempt to represent color. The most straightforward approach is to use an 8-bit dynamic range for each of the three phosphors in a modern CRT--red, green, and blue. Within limits, these 224 possible colors cover most of those discernible to the human eye. Figure 3 shows the use of 24-bit color.
The hue-lightness-saturation (HLS) and hue-saturation-brightness (HSB) models both attempt to map the dynamic-response characteristic of the human retina so that unavoidable quantizations will nevertheless cover color nuances that RGB misses. And, in a pragmatic sense, choosing a color by varying HLS-style parameters is much more natural than using sliders on red, green, and blue.
Color representations can be made with almost any set of tri-stimulus values. Both Digital Image Processing, by W.K. Pratt (John Wiley & Sons, 1978), and The Image Processing Handbook, by J.C. Russ (CRC Press, 1992) provide good discussions of this topic.
The most common approach to representing color images has been to build an 8-bit palette, or indirection table, containing 24-bit color entries that ultimately form the pixels displayed on a screen. The convoluted evolution of display hardware in the computer era is the primary culprit behind the many complexities of these approaches (preferred color model, bit planes, range-matched bit depths, and the like). Palettization and compression cause particular problems for the algorithm described here, so I'll set them aside for now.
Normally, images only exist in space-wasting direct forms while they are being edited and all their information must be quickly at hand. When stored or transmitted, images are usually reduced in size by conversion to a palettized form, by some sort of compression scheme, or both. Some compression algorithms are so effective that they can lower storage requirements to less than one bit per pixel.
Unless these compression schemes are "lossless," they will destroy any authentication information you might embed into an image. Different forms of the sealing algorithm will have to be developed for these cases.
Something is needed to verify that the received image is exactly the same as the one sent, and as a side benefit to prove who sent it. No effort needs to be made to hide or encrypt the image, as you are simply trying to assure that the viewer see what he or she is meant to. (There is a subtle philosophy operating here. When something has been encrypted, it begs to be exposed. But a simple signature can, and most probably will, go completely unnoticed.)
How can you ensure that an image remains unchanged? The easiest way is to use a checksum scheme. Regardless of the given pixel bit depth, you just add all of them up using an unsigned integer-summing variable which equals or exceeds the bit depth of the image pixels. The overflow bit is ignored. The result is a single integer that changes if any single pixel is changed. See Algebraic Methods for Signal Processing and Communications Coding, by R.E. Blahut (Springer-Verlag, 1992), and Digital Signal Transmission, by C.C. Bissell and D.A. Chapman (Cambridge University Press, 1992), for discussions of data integrity.
The probability that any two images will have the same checksum is related to the bit width of that sum. If you only use an 8-bit integer, there is a 1:256 possibility that any two images share the same one. Clearly, you don't want such a high probability that your test will come out positive even if an image has been changed.
If you increase the checksum width to 24 bits, the possibility recedes to a more secure 1:16,777,216; and for that really warm feeling, you can use checksums of bit width nxpixel depth simply by concatenating n adjacent pixels to make larger integers.
Once you have exacted a checksum, it would be nice to embed it into the image itself, so that no separate piece of information exists to aid and abet the potential brigand. How is this done?
Historically, 8-bits-per-pixel for monochrome images was driven primarily by the desire to map system memory to display hardware one byte at a time, speeding memory access. Even 24-bit images are often stored as 32-bit quantities to allow the use of longword transfers when editing or painting. Many of the less-significant bits are, however, purely noise caused by the imaging device. From a visual standpoint, in live "natural" images, the noise at this bit level is entirely masked by the complexity of the scene. Most visual information is carried in the top nybble, with the bottom nybble going along for the ride. Consequently, you can disguise your checksum as noise.
Figure 4 illustrates the basic method of doing this using a monochrome image. You can view the checksum as an array of bits Ncs in length. A uniformly distributed pseudorandom number generator (see Numerical Recipes in C, by W.H. Press et al., Cambridge University Press, 1988, and Seminumerical Algorithms, Second Edition, Vol. 2 of The Art of Computer Programming, by Donald E. Knuth, Addison-Wesley, 1981) is used to map these bits onto a path of randomly selected pixel locations within the limits of the image (you can call this a "random walk").
At each location, the least-significant bit (LSB) of the pixel value is forced to match the value of the corresponding nth checksum bit as n goes from 0 to Ncs--1. The human eye cannot distinguish an LSB shift in intensity on most commercial display systems that have eight or more bits of dynamic range.
Note that, on the average, 50 percent of the pixels will not be changed. This is crucial to the security of the algorithm.
For simplicity, the example algorithm just uses the ASCII values of a seal string truncated to the length of the random-number-generator seed. To ensure that the addresses do not overlap, you should check the random walk immediately after entry and ask the user to enter another one if it contains any overlapping or intersecting pixel addresses.
Since the LSBs at random-walk locations clearly cannot be allowed to contribute to the checksum calculation, you will have to use a three-stage process.
Hey! You're done!
Figure 5 reveals the gray-level interpretation of the previous discussion shown in this example. Any differences are purely printing effects.
Anything which mixes up and shuffles the process I've just described will decrease the probability that an unauthorized person can determine what the seal was. Within probabilistic limits implied by the checksum width, images cannot be modified without destroying an embedded seal, unless that seal is known.
A straightforward checksum algorithm is not completely resistant to purposeful attack. The summing order doesn't affect the outcome, so you can design a "paintbrush" tool that operates by swapping pixels from other locations within the image.
Alternatively, blocks of pixels with a sub-checksum can be replaced by other blocks having the same sub-checksum. For instance, it wouldn't be too tough to replace one face with another.
The checksum process can be made sensitive to pixel placement in any number of ways. Perhaps the simplest here would be to use the random sequence that generated the random walk (it's already running). I'll call the subset of a seal-based number sequence contained within an image a "seal space."
Instead of just adding pixel values as you scan the image, you can add or subtract them based on the bits we encounter as we travel along seal space. Alternatively, you could multiply the pixel by the respective members of the seal space, modulo checksum bit width. Either approach works well. The second way is shown in Listings One and Two .
To make it even harder to determine the seal, you could view the set of pixel bytes as a set of bits instead and add up integers of varying bit widths determined by the random sequence. For example, add two bits to the next seven bits to the next three bits, and so forth. This can be clumsy to mechanize, but it hopelessly loses the sense of the random sequence for anyone who hopes to reconstruct it.
Color images are even better for hiding checksum bits. You can use the same random space to select among the color-vector (for example, red, green, and blue bytes) LSBs. Or, if you're really feeling mean, you could transform each pixel triplet to another color space (RGB to HLS, for instance) and use those dimensions. Nor do you have to use a classic transform: You can pick your own, as long as you remember that the bits ultimately chosen for modification must not impact image quality.
Finally, you can also embed a large number of independent seals into an image, each of which can have an independent set of checksum measurements. This opens up all kinds of possibilities, including the ability to pick a scoundrel from among a trusted group of seal owners.
When a palette is calculated for a 16- or 24-bit image, the resulting colors will not exactly match the originals--they are a compromise. Therefore, if a sealed image is "palettized," it will entirely lose the sealing information coded into the LSBs. So how can you seal a palette image?
If you were to apply the exact monochrome sealing algorithm to an 8-bit indirect color image, the result would look similar to "spike" noise. Modifying the LSB of an arbitrary pixel will shift the color anywhere from a tiny amount to an extreme amount depending on the color that is "next to" it. You can just live with that, or you can rearrange the palette to suit our algorithm. With any "real" image, a palette will contain groups of similar colors, such as those providing shades of green for vegetation, or just the normal shading of brightness that occurs when light strikes any three-dimensional object. The trick is to locate these groups and rebuild the palette such that very similar colors are adjacent in the table.
Once a new palette is built and the image is remapped to it, the 8-bit monochrome sealing algorithm can be used at leisure.
One method is to extract the 128 most-different colors from the palette and assign them to even-numbered indexes. Then search the palette again to find the most-similar color to each of these, placing those in the adjacent odd-numbered indexes. This will work for all but the most pathological of palettes. Finally, this remapping is used to change the content of all the image pixel data so that each points to its original reference color.
A program that illustrates a minor variation of this technique is provided electronically. (This program doesn't work very hard to find the 128 most-separate colors, but it still works well and is a bit faster.)
Figures 6(a) and 6(b) are examples of an 8-bit color-palette image containing 500 embedded seals. They illustrate the results with and without palette reorganization, respectively.
This technique is even more effective when used with longer palettes, since more colors to choose from means a higher probability of finding extremely close color pairs.
Unless it's lossless, don't do it.
The most important place to implement an image-sealing algorithm is at the moment of image creation: within a scanner, still camera, or video system. The video stream is the most demanding application. The design suggested here is one way that a hardware answer can be constructed; see Figure 7.
Remember that the algorithm is at least two stages long. A double-buffered image memory handles this by holding a frame for one cycle while the checksum bits are extracted; these are then added to the video stream on the next cycle when that frame is read out. The penalty is a 1-frame delay in the video stream.
The pixel-address generator counts up pixels from the beginning of a frame. The address is used to write pixel bytes into the input frame buffer, read output pixel bytes from the output buffer, and to tell the walkspace controller when to write out another checksum bit. It also passes a signal that switches the frame-buffer definitions and clears the checksum register in preparation for the next frame.
The walkspace controller contains logic that passes the appropriate bit address (0...checksum length--1) to the checksum control logic when a walkspace address has been reached. The simplest way to implement this is just another frame buffer filled with bit addresses where appropriate, and a NULL flag such as $FF, where not (this approach mirrors the software implementation in Listing One).
The checksum control logic has two functions. It contains two checksum registers that are swapped with the frame buffer I/O definitions. One of these performs the checksum addition function (or its analog), and the other outputs the appropriate bits of the previous checksum to the LSB pixel switch in the outgoing data stream.
The output pixel switch sets the LSB of the outgoing data byte to match the appropriate checksum bit, or passes the data through unchanged if the address is not on a walkspace pixel.
The inverse of this design, a seal-checking machine, would not require the double frame buffer but would otherwise look very similar. Checksums built from the walkspace path would be collected when the checksum was constructed. The two would be compared at the end of the frame.
This algorithm could also be used with ordinary analog VCRs and camcorders. By raising the walk-bit level of the checksum bits to bit 1 or 2 instead of 0, the seal signal can be raised above the noise of the recording system. When seal checking, frame averaging could be used to improve the signal-to-noise ratio. Sensitivity to absolute video level can be reduced by using relative measures of local pixel neighborhoods to set the checksum bits.
Several features of this approach lead me to believe that it is very secure indeed. In order to modify an image, yet maintain the seals intact, an interloper would have to determine the location and order of all the hidden checksum bits, the sequence with which the checksum was constructed, and exactly how many seals are in the image. He would then be able to add the incriminating evidence with his favorite paint program, and reseal the image. Hmmm...
You are therefore limited by the relationship
Equation where n is the maximum number of image seals; m is the pseudorandom modulus and maximum bit width of a seal; Nr and Nc are the height and width of the image, respectively; and r is the percentage of the image you use up for your chunks of seal space.
If m=128 bits, Nr=Nc=128, and you require at least 50 percent of the image to be unmodified, then a maximum of only 64 seals can be embedded.
If the industrious interloper has managed to locate the 50 percent of the seal space he has visible to him (25 percent of the image), perhaps by using his stolen copy of the unsealed image and subtracting to find changed pixels, there are still 4096 bits floating around in 8192 possible locations. Pure permutation tells you that you have 8192!/4096! potential random sequences--an impossibly huge number.
In truth, it must be admitted that the actual number is quite a bit less, limited by how good your pseudo-random-number generator is and how many bits you used in the modulus.
For a perfect generator that does not repeat, the example has only 2128 possible random walks (this number is reduced a bit because we have to choose non-self-intersecting sequences for the first m addresses). Out of this number you have used 64. This leaves the interloper with a much improved 1 in >1030 chance of getting it right. If this isn't good enough for you, nothing prevents you from using a longer modulus.
For larger images, the job is just harder.
Clearly, it is not possible for you to be fooled by having the universe of all possible seals embedded, so as to cover the ones you might have used.
To summarize the security of the techniques presented here, an interloper cannot tell if an image has been sealed, has no way of finding the unchanged LSBs, and cannot blanket your image with all possible seals.
That's safe enough for me.
Figure 1 King John's seal.
Figure 2 Logical structure of an 8-bit monochrome image (pixel bit depth=3).
Figure 3 Logical structure of 24-bit color (pixel bit depth=24).
Figure 4 Disguising your checksum as noise using a monochrome image. (a) Random walk sequence for two nonintersecting seals; (b) fixed modifications due to seal embedding (checksum=00112).
Figure 5 Gray-level interpretation.
Figure 7 Real-time seal machine for 8-bit monochrome digital video.
// <sealimg.c>
// Copyright 1994 by Steve Walton
//
// This implementation measures checksums using all of the upper 7 bits of each
// pixel, without varying the number of bits by random sequence. It does,
// however, ensure order dependence by multiplying sum elements pairwise with
// a pseudo-random sequence and accumulating a sum.
// The overall structure of this program is intended to roughly mirror or
// simulate what could be used as a hardware design.
// A temporary file is used to store "images" of checksum bits and walk
// locations. Obviously, this could be done in extended memory, but this method
// will work on 286-class machines with little or no RAM running without a swap
// manager, and is independent of image size. Up to 255 using checksum lengths
// up to 256 bits long are possible within the limits of this structure.
// The temporary disk file is roughly twice the size of image being tested
// for seals. Named <temp> and placed in the launch path, it is deleted after
// use. When filling the image with seal checksum bits, the sealspace map is
// used to embed them in one pass through the image; the map tells us which
// bit for which seal is to be forced into the pixel LSB.
// To reduce (apparent) code complexity and improve readability, this program
// is written using static global variables for file pointers, control
// variables, and so forth. Code-crafting could improve the structure a great
// deal, but this form is probably better for illustrating the underlying
// algorithms. All user-written functions used in this program are contained
// in this listing.
// Targa image format is used for file I/O, primarily because it is as
// universal as TIFF and MUCH easier to use on a casual basis. Hopefully, the
// structure is semi-self-evident from the code.
// Written with and compiled by Microsoft QuickC for Windows v1.00
// TARGA is a registered trademark of Truevision, Inc.
// TGA is a registered trademark of Truevision, Inc.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <process.h>
#include <malloc.h>
#include <math.h>
// Structures must be stored byte-aligned! Compile with switch /Zp1 (Microsoft)
// or the equivalent.
typedef unsigned long ULONG;
typedef unsigned short USHORT;
typedef unsigned short BOOL;
typedef unsigned char BYTE;
// Truevision TARGA file header format
typedef struct {
BYTE idLength; // Identifies number of bytes in optional Targa Field 6
BYTE colorMapType; // Type of color map (0=no color map, 1=color map used)
BYTE imageType; // Type of image (1=uncompress color-mapped,
// 2=24-bit direct, 3= monochrome)
USHORT firstEntry; // Index of first color map entry (usually 0)
USHORT mapLength; // Length of color map (number of colors)
BYTE entrySize; // Size of color map entry (bits)
USHORT xOrigin; // Horiz coord of L-L image corner on display
USHORT yOrigin; // Vert coord of L-L image corner on display
USHORT width; // Width of the image in pixels
USHORT height; // Height of the image in pixels
BYTE pixDepth; // Number of bits in each pixel location
BYTE imageDesc; // Alpha Channel bits or overlay bits
} tgaHeader_t;
// Truevision TARGA RGB triplet format
typedef struct {
BYTE blu; // 8-bit Blue component
BYTE grn; // 8-bit Green component
BYTE red; // 8-bit Red component
} rgbTriplet_t;
typedef struct { // The per-pixel-address descriptor
BYTE sealNum; // ... Index number of seal
BYTE bitNum; // ... bit number (0=LSB) of the checksum
} sealSpace_t;
typedef union { // Mechanizes our VERY SIMPLE pseudo-random-number
ULONG bits32; // generator seeds
char asciiChar[4]; // The characters are kept for reference.
} seal_t;
#define TRUE 1
#define FALSE 0
#define MONO 3
#define PALETTE 1
#define NOSEAL 0xFF
// -------------- Global Variable List -------------------------------
ULONG
checksum[256]
;
seal_t
sealArray[255]; // Contains the seeds for each seal
FILE
*fpIn, // Input file pointer
*fpOut // Output file pointer
;
char
inFileName[80], // Input file name string (allow 80 bytes)
outFileName[80] // Output file name string (allow 80 bytes)
;
////////////////////////////
// F u n c t i o n s //
////////////////////////////
//-----------------------u r a n d D o u b l e ()------------------------------
// A pseudo-random number generator designed to return floating-point
// quantities as a percentage of a passed range argument. This is the standard
// linear congruential generator which uses the recurrence relation i(j+1) =
// mod(m)[a * i(j) + c], where m is the modulus, a is the muliplier,
// and c is the offset. The randomness of these sequences is very dependent
// upon a, m, and c. The value of i(0) is called the seed.
#define URANDDOUBLE_MULTIPLIER 2416L // Multiplier
#define URANDDOUBLE_OFFSET 374441L // Offset
#define URANDDOUBLE_MODULUS 1771875L
static unsigned long urandDoubleSeed = 3456L; // global static unsigned
double urandDouble( double range ){ // long seed
urandDoubleSeed = (urandDoubleSeed * URANDDOUBLE_MULTIPLIER +
URANDDOUBLE_OFFSET) % URANDDOUBLE_MODULUS;
return( ((double)urandDoubleSeed * (range)) / (double)URANDDOUBLE_MODULUS );
}
//---------------------------u r a n d W A ()----------------------------------
// A pseudo-random number generator designed to return 16-bit quantities. This
// is an arrayed function of up to 256 outputs. This is the standard linear
// congruential generator which uses the recurrence relation i(j+1) = mod(m)[a
// * i(j) + c], where m is the modulus, a is muliplier, and c is the offset.
// The randomness of these sequences is very dependent upon a, m, and c.
// The value of i(0) is called the seed.
#define URANDWA_MULTIPLIER 2416L // Multiplier
#define URANDWA_OFFSET 374441L // Offset
#define URANDWA_MODULUS 1771875L
static unsigned long
urandWASeed[256]; // global static unsigned long seed
USHORT urandWA( short index ){
urandWASeed[index] = (urandWASeed[index] * URANDWA_MULTIPLIER +
URANDWA_OFFSET) % URANDWA_MODULUS;
return( (USHORT)( (double)urandWASeed[index] * 65536.0 /
(double)URANDWA_MODULUS ) );
}
//==================== s o l i c i t S e a l s () =============================
// Gets up to 255 4-character sealing strings from the user and fills the
// file pointed to by <sealSpace> with seal# and bit# information. We are using
// 32-bit checksums, and the walk space is driven by urandWord()
short solicitSeals( FILE *sealSpace, long sealSpaceLength ){
BOOL
sealGood = TRUE,
done = FALSE
;
short
i,
numSeal=0
;
long walkAddress;
char
temp
;
sealSpace_t
sealPix
;
seal_t
inSeal
;
printf( "\n----Seal entry----\n" );
printf( "Each four characters will be taken as a seal. Each seal's
validity is\n" );
printf( "checked as it is entered. Invalid (intersecting) seals are
not accepted.\n" );
printf( "You may enter up to 255 seals (indices are 0..254)\n" );
while( !done ){
printf( "Enter seal %d (ESC to end): ", numSeal );
i=0;
while( i < 4 ){
temp = (char)getch();
if( temp == 27 ){
done = TRUE;
break;
} else {
inSeal.asciiChar[i] = temp;
printf( "-" );
i++;
}
}
if( !done ){
printf( "%c Checking %c%c%c%c...", 7, inSeal.asciiChar[0],
inSeal.asciiChar[1], inSeal.asciiChar[2], inSeal.asciiChar[3] );
// First, check the sealspace for any of these locations...
sealGood = TRUE;
urandDoubleSeed = inSeal.bits32 % URANDDOUBLE_MODULUS;
for( i=0; i<32; i++ ){
walkAddress = (long)urandDouble( sealSpaceLength );
if( walkAddress == sealSpaceLength ) walkAddress = sealSpaceLength-1;
fseek( sealSpace, walkAddress*sizeof(sealSpace_t), SEEK_SET );
fread( &sealPix, sizeof( sealSpace_t ), 1, sealSpace );
if( sealPix.sealNum != NOSEAL ){
sealGood = FALSE;
break;
}
}
if( sealGood ){
printf( "ok -- embedding...\n" );
sealArray[numSeal].bits32 = inSeal.bits32; // Copy into seal array
// embed this seal into the sealspace map
urandDoubleSeed = inSeal.bits32 % URANDDOUBLE_MODULUS;
for( i=0; i<32; i++ ){
walkAddress = (long)urandDouble( sealSpaceLength );
if( walkAddress == sealSpaceLength ) walkAddress=sealSpaceLength-1;
sealPix.sealNum = (BYTE)numSeal; // Keep sealArray index in the map
sealPix.bitNum = (BYTE)i; // Keep bit number in the map
fseek( sealSpace, walkAddress*sizeof(sealSpace_t), SEEK_SET );
fwrite( &sealPix, sizeof( sealSpace_t ), 1, sealSpace );
}
numSeal++;
if( numSeal == 255 ) done = TRUE; // Limit number of seals
} else {
printf( "no. Try another.\n" );
}
} // End checking and embedding section
}
printf( "\nYou have embedded %d seals.\n", numSeal );
return( numSeal );
}
//======================= o p e n F i l e s () ================================
// Open image files. Test each file for validity and return FALSE if something
// is wrong. There are all sorts of clever ways to avoid using a "goto"
// statement, and I support most of them. This is one of the places where its
// use is justified to generate short, quick code.
BOOL openFiles( void ){
tgaHeader_t *hdr;
// Go get temporary storage for the header so we can test it for validity
hdr = (tgaHeader_t *)malloc( sizeof(tgaHeader_t) );
if( hdr == NULL ){
printf( "Your system's seriously ill! Can't allocate 18 bytes
of dynamic memory!" );
goto bugout;
}
// OPEN THE INPUT FILE
printf( "Enter complete input image file name: " );
scanf( "%s", &inFileName[0] );
fpIn = fopen( &inFileName[0], "rb" ); // Attempt to open the input file
if( fpIn == NULL ){
printf( "Problem opening file %s\n", inFileName );
goto errorExitCloseFile;
}
fread( hdr, sizeof(tgaHeader_t), (size_t)1, fpIn ); // Read the input block
rewind( fpIn ); // Reset file pointer to zero
if( hdr->imageType != MONO && hdr->imageType != PALETTE ){
printf( "Input image is not Targa monochrome or palette." );
goto errorExitCleanAll;
}
if( hdr->imageType == MONO &&
(hdr->mapLength != 0 || hdr->colorMapType != 0 || hdr->pixDepth != 8 ||
hdr->entrySize != 0 )){
printf( "Corrupted monochrome image file." );
goto errorExitCleanAll;
}
if( hdr->imageType == PALETTE &&
(hdr->mapLength != 256 || hdr->colorMapType == 0 ||
hdr->pixDepth != 8 || hdr->entrySize != 24 ) ){
printf( "Not an appropriate 8-bit palette image file." );
goto errorExitCleanAll;
}
// OPEN THE OUTPUT FILE
printf( "Enter output image name: " );
scanf( "%s", &outFileName[0] );
fpOut = fopen( &outFileName[0], "wb" ); // Attempt to open the output file
if( fpOut == NULL ){
printf( "Problem opening file %s\n", outFileName );
goto errorExitCloseFile;
}
// If we've gotten this far, it's likely that everything is OK and we can
// get back to business...
return( TRUE );
errorExitCleanAll: // Error exit point
free( hdr );
errorExitCloseFile: // Another error exit point
fcloseall();
bugout: // Get outta here!
return( FALSE );
}
//=========================== m a i n () =====================================
// This program opens an 8-bit grey or 8-bit color mapped Targa file, reads it
// in row-by-row, and applies a list of seals to it.
void main( void ){
BYTE
*rowIn, // Pointer to row of input image pixels
*rowOut // Pointer to row of output image pixels
;
short
i,j,k, // Temporary index variables
numSeals // Total number of seals to check for in the image
;
long
sealSpaceLength // Total number of pixels in the input image.
;
FILE
*sealSpace // File pointer to temporary "seal space frame" image file
;
tgaHeader_t
inFileHeader // Will contain input file Targa header
;
sealSpace_t
*sealRow // Pointer to row of seal space elements
;
rgbTriplet_t
*palette // Pointer to a palette full of rgb triplets
;
// Print out the program identification and default values
printf( "<sealimg.c>\nCopyright 9/20/94 by Steve Walton\n" );
if( !openFiles() ) exit(0); // Get the files from the user and open them
fread( &inFileHeader, sizeof(tgaHeader_t), (size_t)1, fpIn );
sealSpaceLength = (long)inFileHeader.width * (long)inFileHeader.height;
sealSpace = fopen( "temp", "wb+" ); // Open sealspace file for random R/W
sealRow = (sealSpace_t *)malloc( sizeof( sealSpace_t ) *
inFileHeader.width );
printf( "Clearing sealspace...\n" );
// Clear temporary file with seal walkspace data, since it will be filled
for( i=0; i<(short)inFileHeader.width; i++ ){
sealRow[i].sealNum = NOSEAL;
sealRow[i].bitNum = 0;
}
for( j=0; j<(short)inFileHeader.height; j++ ){ // Clear the sealspace file
fwrite( sealRow,sizeof(sealSpace_t),(size_t)inFileHeader.width,sealSpace );
}
// Now that we have a place to put them, fill sealSpace with valid seals
// gotten from the user. Remember that the array containing the actual seal
// strings is the global static array <sealArray[255]>
numSeals = solicitSeals( sealSpace, sealSpaceLength );
// Allocate some memory for all of our image manipulation to come...
rowIn = (BYTE *)malloc( inFileHeader.width );
rowOut = (BYTE *)malloc( inFileHeader.width );
// We will now go through the image and calculate the seal-warped checksums.
// Checksums are modulo-32, based on an iterative multiply-accumulate
// operation of the form cs32 <- (ran16 * (pixel>>1) ) % 0xFFFFFFFF + cs32
// where cs32 is the check sum "summing" variable, pixel is the 8-bit image
// pixel data at address N, and ran16 is the upper 16 bits of the Nth
// iteration of a 32-bit linear congruential generator. The modulo 0xFFFFFFFF
// is obtained simply by using unsigned long integer arithmetic.
printf( "Measuring commuted checksums...\n" );
for( j=0; j<numSeals; j++ ){
checksum[j] = 0L; // Clear all of the checksums
urandWASeed[j] = sealArray[j].bits32 % URANDWA_MODULUS;
// Set seeds to values implied by seals
}
fseek( fpIn, sizeof(tgaHeader_t) + (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ), SEEK_SET );
for( i=0; i<(short)inFileHeader.height; i++ ){
fread( rowIn, (size_t)1, (size_t)inFileHeader.width, fpIn );
for( j=0; j<(short)inFileHeader.width; j++ ){
for( k=0; k<numSeals; k++ ){
checksum[k] += (ULONG)urandWA(k) * (ULONG)(rowIn[j]>>1);
}
}
}
// Get the output image ready to go. Put a copy of the input file header at
// the beginning of the output file, and copy the color palette over if it
// is a palette-type image.
fseek( fpOut, 0, SEEK_SET ); // Reset output file pointer to zero
fwrite( &inFileHeader, sizeof( tgaHeader_t ), (size_t)1, fpOut );
if( inFileHeader.imageType == PALETTE ){
palette = (rgbTriplet_t *)malloc( (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ) );
fseek( fpIn, sizeof(tgaHeader_t), SEEK_SET ); // Set input pointer
fread( palette, sizeof( rgbTriplet_t ),
(size_t)inFileHeader.mapLength, fpIn ); // Read palette
fseek( fpOut, sizeof(tgaHeader_t), SEEK_SET ); // Set output pointer
fwrite( palette, sizeof( rgbTriplet_t ), (size_t)inFileHeader.mapLength,
fpOut ); // Write palette
free( palette ); // Free this -- we don't use the palette
}
// Set the file pointers of all files to the beginning of the image data
fseek( fpIn, sizeof(tgaHeader_t) + (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ), SEEK_SET );
fseek( fpOut, sizeof(tgaHeader_t) + (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ), SEEK_SET );
fseek( sealSpace, 0, SEEK_SET );
// Go through the image and embed checksums. Use the sealspace map to tell
// which bit of which checksum to place with each pixel...
printf( "Embedding checksums into image data...\n" );
for( i=0; i<(short)inFileHeader.height; i++ ){
fread( rowIn, (size_t)1, (size_t)inFileHeader.width, fpIn );
fread( sealRow,sizeof(sealSpace_t), (size_t)inFileHeader.width,sealSpace );
for( j=0; j<(short)inFileHeader.width; j++ ){
if( sealRow[j].sealNum == NOSEAL ){
rowOut[j] = rowIn[j];
} else {
rowOut[j] = (BYTE)(
(ULONG)(rowIn[j] & 0xFE) |
(0x01L & (checksum[ sealRow[j].sealNum] >> sealRow[j].bitNum ))
);
}
}
fwrite( rowOut, (size_t)1, (size_t)inFileHeader.width, fpOut );
}
free( rowIn );
free( rowOut );
free( sealRow );
fcloseall();
system( "del temp" );
printf( "Execution complete.\n" );
}
// <testseal.c> Copyright 1994 by Steve Walton
// This implementation measures checksums using all of the upper 7 bits of each
// pixel, without varying number of bits by random sequence. It does, however,
// ensure order dependence by multiplying sum elements pairwise with a
// pseudo-random sequence and accumulating a sum. The overall structure of this
// program is intended to roughly mirror or simulate what could be used as
// a hardware design. A temporary file is used to store "images" of checksum
// bits and walk locations. Obviously, this could be done in extended memory,
// but this method will work on 286-class machines with little or no RAM
// running without a swap manager, and is independent of image size. Up to 255
// using checksum lengths up to 256 bits long are possible within the limits
// of this structure. The temporary disk file is roughly twice the size of the
// image being tested for seals. Named <temp> and placed in the launch path, it
// is deleted after use. When checking the image for seal checksum bits, the
// sealspace map is used to find them in one pass through the image; the map
// tells us which bit for which seal is to be forced into the pixel LSB. To
// reduce (apparent) code complexity and improve readability, this program is
// written using static global variables for file pointers, control variables,
// and so forth. Code-crafting could improve the structure a great deal, but
// this form is probably better for illustrating the underlying algorithms.
// All user-written functions used in this program are contained here.
// Targa image format is used for file I/O, primarily because it is as
// universal as TIFF and MUCH easier to use on a casual basis. Hopefully, the
// structure is semi-self-evident from the code. Written with and compiled by
// Microsoft QuickC for Windows v1.00. TARGA is a registered trademark of
// Truevision, Inc. TGA is a registered trademark of Truevision, Inc.
//
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <process.h>
#include <malloc.h>
#include <math.h>
// Structures must be stored byte-aligned! Compile with switch /Zp1 (Microsoft)
// or equivalent.
typedef unsigned long ULONG;
typedef unsigned short USHORT;
typedef unsigned short BOOL;
typedef unsigned char BYTE;
// Truevision TARGA file header format
typedef struct {
BYTE idLength; // Identifies number of bytes in optional Targa Field 6
BYTE colorMapType; // Type of color map (0=no color map, 1=color map used)
BYTE imageType; // Type of image (1=uncompress color-mapped,
// 2=24-bit direct, 3=monochrome)
USHORT firstEntry; // Index of first color map entry (usually 0)
USHORT mapLength; // Length of color map (number of colors)
BYTE entrySize; // Size of color map entry (bits)
USHORT xOrigin; // Horiz coord of lower-left image corner on a display
USHORT yOrigin; // Vert coord of lower-left image corner on a display
USHORT width; // Width of the image in pixels
USHORT height; // Height of the image in pixels
BYTE pixDepth; // Number of bits in each pixel location
BYTE imageDesc; // Alpha Channel bits or overlay bits
} tgaHeader_t;
// Truevision TARGA RGB triplet format
typedef struct {
BYTE blu; // 8-bit Blue component
BYTE grn; // 8-bit Green component
BYTE red; // 8-bit Red component
} rgbTriplet_t;
typedef struct { // per-pixel-address descriptor for keeping embedded checksum
bit locations
BYTE sealNum; // Index number of seal associated with the checksum partially
// embedded at this location
BYTE bitNum; // Bit number (0=LSB) of the checksum associated with this seal
} sealSpace_t;
typedef union { // Mechanizes pseudo-random-number generator seeds
ULONG bits32;
char asciiChar[4]; // The characters are kept for reference.
} seal_t;
#define TRUE 1
#define FALSE 0
#define MONO 3
#define PALETTE 1
#define NOSEAL 0xFF
// -------------- Global Variable List -------------------------------
ULONG
checksum[256], // array of 32-bit image checksums, implied by seals
checksumEmbedded[256] // array of 32-bit image checksums stripped from
// embedded walk sequences
;
seal_t
sealArray[255]; // Contains the seeds for each seal
FILE
*fpIn, // Input file pointer
*fpOut // Output file pointer
;
char
inFileName[80], // Input file name string (allow 80 bytes)
outFileName[80] // Output file name string (allow 80 bytes)
;
////////////////////////////
// F u n c t i o n s //
////////////////////////////
//======================== u r a n d D o u b l e () ===========================
// Pseudo-random number generator designed to return floating-point quantities
// as a percentage of a passed range argument. This is the standard linear
// congruential generator which uses the recurrence relation i(j+1) = mod(m)[a
// * i(j) + c], where m is the modulus, a is the muliplier, and c is offset.
// The randomness of these sequences is very dependent upon a, m, and c.
// The value of i(0) is called the seed.
//
#define URANDDOUBLE_MULTIPLIER 2416L // Multiplier
#define URANDDOUBLE_OFFSET 374441L // Offset
#define URANDDOUBLE_MODULUS 1771875L
static unsigned long urandDoubleSeed = 3456L;
double urandDouble( double range ){
urandDoubleSeed = (urandDoubleSeed * URANDDOUBLE_MULTIPLIER +
URANDDOUBLE_OFFSET) % URANDDOUBLE_MODULUS;
return( ((double)urandDoubleSeed * (range)) / (double)URANDDOUBLE_MODULUS );
}
//========================= u r a n d W A () =================================
// A pseudo-random number generator designed to return 16-bit quantities. This
// is an arrayed function of up to 256 outputs. This is the standard linear
// congruential generator which uses the recurrence relation i(j+1) = mod(m)[a
// * i(j) + c], where m is the modulus, a is the muliplier, and c is offset.
// The randomness of these sequences is very dependent upon a, m, and c.
// The value of i(0) is called the seed.
//
#define URANDWA_MULTIPLIER 2416L // Multiplier
#define URANDWA_OFFSET 374441L // Offset
#define URANDWA_MODULUS 1771875L
static unsigned long
urandWASeed[256]; // global static unsigned long seed
USHORT urandWA( short index ){
urandWASeed[index] = (urandWASeed[index] * URANDWA_MULTIPLIER +
URANDWA_OFFSET) % URANDWA_MODULUS;
return( (USHORT)( (double)urandWASeed[index] * 65536.0 /
(double)URANDWA_MODULUS ) );
}
//========================= s o l i c i t S e a l s () =====================
// Gets up to 255 4-character sealing strings from the user and fills the file
// pointed to by <sealSpace> with seal# and bit# information. We are using
// 32-bit checksums, and the walk space is driven by urandWord()
short solicitSeals( FILE *sealSpace, long sealSpaceLength ){
BOOL
sealGood = TRUE,
done = FALSE
;
short
i, // Temporary index variable
numSeal=0
;
long
walkAddress;
char
temp
;
sealSpace_t
sealPix
;
seal_t
inSeal
;
printf( "\n---- Seal Test List Entry ----\n" );
printf( "Each four characters entered will be taken as a seal. \n" );
printf( "You may submit up to 255 seals for testing (indices are 0..254)\n" );
printf( "If you get self-intersections, at least two seals in your list\n" );
printf( "are mutually exclusive, one of which cannot be present.\n" );
while( !done ){
printf( "Enter seal %d (ESC to end): ", numSeal );
i=0;
while( i < 4 ){
temp = (char)getch();
if( temp == 27 ){
done = TRUE;
break;
} else {
inSeal.asciiChar[i] = temp;
printf( "-" );
i++;
}
}
if( !done ){
printf( "%c (checking for intersections...", 7 );
// First, check the sealspace for any of these locations...
sealGood = TRUE;
urandDoubleSeed = inSeal.bits32 % URANDDOUBLE_MODULUS;
for( i=0; i<32; i++ ){
walkAddress = (long)urandDouble( sealSpaceLength );
if( walkAddress == sealSpaceLength ) walkAddress = sealSpaceLength-1;
fseek( sealSpace, walkAddress*sizeof(sealSpace_t), SEEK_SET );
fread( &sealPix, sizeof( sealSpace_t ), 1, sealSpace );
if( sealPix.sealNum != NOSEAL ){
sealGood = FALSE;
break;
}
}
if( sealGood ){
printf( "ok.)\n" );
sealArray[numSeal].bits32 = inSeal.bits32;
// embed this seal into the sealspace map
urandDoubleSeed = inSeal.bits32 % URANDDOUBLE_MODULUS;
for( i=0; i<32; i++ ){
walkAddress = (long)urandDouble( sealSpaceLength );
if( walkAddress == sealSpaceLength ) walkAddress=sealSpaceLength-1;
sealPix.sealNum = (BYTE)numSeal; // Keep sealArray index in the map
sealPix.bitNum = (BYTE)i; // Keep bit number in the map
fseek( sealSpace, walkAddress*sizeof(sealSpace_t), SEEK_SET );
fwrite( &sealPix, sizeof( sealSpace_t ), 1, sealSpace );
}
numSeal++;
} else {
printf( "no. Try another.)\n" );
}
} // End checking and embedding section
}
printf( "\nYou have submitted %d seals for testing.\n", numSeal );
return( numSeal );
}
//============================ o p e n F i l e s () ==========================
// Open image files. Test each file for validity and return FALSE if something
// is wrong. There are all sorts of clever ways to avoid using a "goto"
// statement, and I support most of them. This is one of the places where
// its use is justified to generate short, quick code.
BOOL openFiles( void ){
tgaHeader_t *hdr;
// Get temporary storage for the header so we can test it for validity
hdr = (tgaHeader_t *)malloc( sizeof(tgaHeader_t) );
if( hdr == NULL ){
printf( "Your system's seriously ill! Can't allocate 18 bytes
of dynamic memory!" );
goto bugout;
}
// OPEN THE INPUT FILE
printf( "Enter complete input image file name: " );
scanf( "%s", &inFileName[0] );
fpIn = fopen( &inFileName[0], "rb" );
if( fpIn == NULL ){
printf( "Problem opening file %s\n", inFileName );
goto errorExitCloseFile;
}
fread( hdr, sizeof(tgaHeader_t), (size_t)1, fpIn );
rewind( fpIn );
if( hdr->imageType != MONO && hdr->imageType != PALETTE ){
printf( "Input image is not Targa monochrome or palette." );
goto errorExitCleanAll;
}
if( hdr->imageType == MONO &&
(hdr->mapLength != 0 || hdr->colorMapType != 0 || hdr->pixDepth != 8 ||
hdr->entrySize != 0 )){
printf( "Corrupted monochrome image file." );
goto errorExitCleanAll;
}
if( hdr->imageType == PALETTE &&
(hdr->mapLength != 256 || hdr->colorMapType == 0 ||
hdr->pixDepth != 8 || hdr->entrySize != 24 ) ){
printf( "Not an appropriate 8-bit palette image file." );
goto errorExitCleanAll;
}
// If we've gotten this far, it's likely that everything is OK and we can
// get back to business...
return( TRUE );
errorExitCleanAll: // Error exit point
free( hdr );
errorExitCloseFile: // Another error exit point
fcloseall();
bugout: // Get outta here!
return( FALSE );
}
////////////////////////////
// m a i n () //
////////////////////////////
//==========================================================================
// This program opens either an 8-bit grey or 8-bit color-mapped Targa image,
// reads it in row-by-row, and checks for presence of a list of embedded seals.
void main( void ){
BYTE
*rowIn // Pointer to row of input image pixels
;
short
i,j,k, // Temporary index variables
numSeals // Total number of seals to check for in the image
;
long
sealSpaceLength // Total number of pixels in the input image.
;
FILE
*sealSpace // File pointer to temporary "seal space frame" image file
;
tgaHeader_t
inFileHeader // Will contain input file Targa header
;
sealSpace_t
*sealRow // Pointer to row of seal space elements
;
// Print out the program identification and default values
printf( "<testseal.c>\nCopyright 9/20/94 by Steve Walton\n" );
if( !openFiles() ) exit(0); // Get the files from the user and open them
fread( &inFileHeader, sizeof(tgaHeader_t), (size_t)1, fpIn );
sealSpaceLength = (long)inFileHeader.width * (long)inFileHeader.height;
sealSpace = fopen( "temp", "wb+" ); // Open sealspace file for random R/W
sealRow = (sealSpace_t *)malloc( sizeof( sealSpace_t )*inFileHeader.width);
printf( "Clearing sealspace...\n" );
// Clear the temporary file with the seal walkspace data
for( i=0; i<(short)inFileHeader.width; i++ ){
sealRow[i].sealNum = NOSEAL;
sealRow[i].bitNum = 0;
}
for( j=0; j<(short)inFileHeader.height; j++ ){
fwrite( sealRow, sizeof(sealSpace_t),(size_t)inFileHeader.width,sealSpace);
}
// Now that we have a place to put them, fill sealSpace with valid seals
// gotten from the user. Remember that the array containing the actual seal
// strings is the global static array <sealArray[255]>
numSeals = solicitSeals( sealSpace, sealSpaceLength );
// Allocate some memory for all of our image manipulation to come...
rowIn = (BYTE *)malloc( inFileHeader.width );
//rowOut = (BYTE *)malloc( inFileHeader.width );
// We will now go through the image and calculate seal-warped checksums.
// Checksums are modulo-32, based on an iterative multiply-accumulate
// operation of the form cs32 <- (ran16 * (pixel>>1) ) % 0xFFFFFFFF + cs32
// where cs32 is the check sum "summing" variable, pixel is the 8-bit image
// pixel data at address N, and ran16 is the upper 16 bits of the Nth
// iteration of a 32-bit linear congruential generator. The modulo 0xFFFFFFFF
// is obtained simply by using unsigned long integer arithmetic.
printf( "Measuring checksums...\n" );
for( j=0; j<numSeals; j++ ){
checksum[j] = 0L; // Clear all of the checksums
urandWASeed[j] = sealArray[j].bits32 % URANDWA_MODULUS;
}
fseek( fpIn, sizeof(tgaHeader_t) + (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ), SEEK_SET );
for( i=0; i<(short)inFileHeader.height; i++ ){
fread( rowIn, (size_t)1, (size_t)inFileHeader.width, fpIn );
for( j=0; j<(short)inFileHeader.width; j++ ){
for( k=0; k<numSeals; k++ ){
checksum[k] += (ULONG)urandWA(k) * (ULONG)(rowIn[j]>>1);
}
}
}
// Set the file pointers of all files to the beginning of the image data
fseek( fpIn, sizeof(tgaHeader_t) + (inFileHeader.mapLength *
sizeof( rgbTriplet_t ) ), SEEK_SET );
fseek( sealSpace, 0, SEEK_SET );
// go through the image and embed checksums. Use the sealspace map to tell
// which bit of which checksum to place with each pixel...
printf( "Checking for embedded checksums in image data...\n" );
for( i=0; i<numSeals; i++ ) checksumEmbedded[i] = 0L;
for( i=0; i<(short)inFileHeader.height; i++ ){
fread( rowIn, (size_t)1, (size_t)inFileHeader.width, fpIn );
fread( sealRow, sizeof(sealSpace_t),(size_t)inFileHeader.width,sealSpace );
for( j=0; j<(short)inFileHeader.width; j++ ){
if( sealRow[j].sealNum != NOSEAL ){
checksumEmbedded[sealRow[j].sealNum] |= (ULONG)( rowIn[j] & 0x01 )
<< sealRow[j].bitNum;
}
}
}
for( i=0; i<numSeals; i++ ){
if( checksum[i] == checksumEmbedded[i] ){
printf( "#%d, %c%c%c%c, is present\n", i,
sealArray[i].asciiChar[0], sealArray[i].asciiChar[1],
sealArray[i].asciiChar[2], sealArray[i].asciiChar[3] );
} else {
printf( "#%d, %c%c%c%c, is not present\n", i,
sealArray[i].asciiChar[0], sealArray[i].asciiChar[1],
sealArray[i].asciiChar[2], sealArray[i].asciiChar[3] );
}
}
free( rowIn );
free( sealRow );
fcloseall();
system( "del temp" );
printf( "Execution complete.\n" );
}
Copyright © 1995, Dr. Dobb's Journal