More About Jittering
This page is for those who would like to know more about how jittering is done.
Although different GISes use different formats and maintain varying amounts of information about vector figures, at bottom they are in "spaghetti representation:" sequences of connected points, with each point given as a pair of X,Y coordinates.
The biggest difference among formats is in how the coordinates are maintained: some, like MapInfo, use integer values, and others, like ArcView, use floating point values. The integer values usually describe relative locations within a box surrounding the area of interest. MapInfo, for instance, specifies the box endpoints with floating point precision, then divides up the sides of the box into two billion tiny segments. The coordinates refer to these segments.
Despite these differences in how numbers are represented, jittering works basically the same way. It's somewhat more difficult to carry out in floating point, so I will describe that here. First, let's establish some terminology concerning floats.
A floating point value is a number like 4.379 E7, meaning 4.379 times ten to the seventh power (ten million). For consistency, computers first normalize floating point values so that the first digit (preceding the decimal point) is a zero and the second digit (immediately following the decimal point) is, if possible, not zero. Thus 4.379 E7 would be normalized to 0.4379 E8.
In the normalized representation, the 0.4379 is the mantissa and the E8 is the exponent. (Either or both of the mantissa and exponent can be negative. For instance, -0.278 E-1 represents -0.0278.)
There are some exceptions, of which the most notable is zero. All numbers of the form 0.0 E<anything> represent zero, but technically none of them are normalized, because the digit following the decimal point is zero. That's too bad, because it creates a nasty complication, but there are ways to handle it.
Because computers usually use a fixed amount of space (a register) to compute with numbers, the mantissas of normalized floats always have the same number of digits. To illustrate, let's suppose that exactly six digits are used. (This is not true for most computers today, but it's good enough to illustrate what's going on.)
Suppose, then, that we want to hide some information in a six-digit float. Perhaps the simplest way is to select, once and for all, some of the digits. If we number their positions one through six, beginning with the decimal point, then changing digit six changes the number the least, whereas changing digit one changes the number tremendously.
It is therefore natural to hide the message in the last few digits, perhaps digits five and six. However, the sixth digit is a risky one to use: many operations with numbers are not perfectly precise and might change the last digit slightly. Therefore it would be wise not to rely on digit six, but perhaps to use digits four and five.
Assuming the message we want to hide has been encoded as a long string of digits (0 through 9), we would proceed by biting off a two-digit chunk and simply sticking it into digits four and five of the number.
For example, if our message begins 30976... and the number we will jitter is -0.278499 E-1, then:
- Bite off the beginning "30" of the message.
- Take the mantissa (ignoring its minus sign) and wipe out the values in the fourth and fifth places: 0.278__9.
- Fill in the fourth and fifth places with "30": 0.278309.
- Reassemble the number by bringing back its sign and exponent: -0.278309 E-1.
In this example, jittering the value -.00278499 by "30" has changed it to -0.00278309.
To read the message digits back from the jittered value is even easier: just inspect the fourth and fifth digits of the mantissa: -0.278309.
The exception, as noted above, is zero. The problem is that this number gives us no sense of scale: how much is a small amount to jitter? It depends on the context. The quick and easy solution, although not the best, is to assume the very smallest possible exponent. For instance, let us further suppose that our hypothetical computer can handle two-digit exponents (not counting sign). Thus the smallest possible exponent is -99. Putting a "30" into a zero value, then, we would end up with 0.000300 E-99.
Stashing a long message into a vector figure is now easy. At the spaghetti representation level, the figure is just a sequence (x1, y1), (x2, y2), ...., and the message is just a sequence abcde... of digits (each letter represents a value between 0 and 9). So, taking the coordinates as they come, we would jitter ab into x1, cd into y1, ef into x2, and so on.
That's all well and good, but when you turn to programming this algorithm, you might get stuck: most programming languages do not provide procedures for normalizing floats, for picking them apart into exponents and mantissas, for changing individual digits, or for reassembling the pieces. The trick is to rewrite each of these basic operations in terms of more familiar and commonly-supported arithmetic operations.
It is at this point we should acknowledge that most computers use base two, not base ten, to represent floats. The standard is the IEEE format. An IEEE double-precision float uses 52 binary digits for the mantissa, 10 digits for the exponent, and one more bit for each of the signs, for a total of 64 bits: a nice multiple of the 16-, 32-, or 64-bit word length natural to most machines.
Actually, we don't need to work in base two, but by doing so we can avoid various problems of rounding and conversion. That lets us tap into all the precision that is really there.
To develop the jittering functionality, I wrote three low-level routines:
 | Number.SetBits. This routine is given a sequence of binary digits (a bitmap), a starting location in the sequence, a floating point number, a starting bit position (the most significant bit, or "MSB"), and an ending bit position (the least significant bit, or "LSB"). It copies the bitmap, beginning at the starting location, into the specified bits of the number. This is the jittering operation. |
| Number.GetBits. This routine is given the same information, but this time copies the digits from the number into the bitmap. This is the operation of reading a jittered number. |
| Number.AsIEEEHex represents a double-precision number in hexadecimal as a signed mantissa followed by a signed exponent. This is extremely useful during program development to verify that the computer is behaving as expected. For instance, pi in base ten is approximately 3.14159265358979324; Number.AsIEEEHex displays this value as " 0.c90f daa2 2168 c H+2". This is readily converted into binary because each hexadecimal digit stands for a unique sequence of four bits: c is 1100, 9 is 1001, and so on. Thus the IEEE floating point representation of pi begins 0.1100 1001 0000 1111..., which is slightly greater than 3/4, and the exponent is 2, yielding a value slightly greater than 3/4 * 2^2 = 3. That looks about right. |
These routines are available through the links above, exactly as written, warts and all. They are in Avenue, ArcView 3.x's scripting language. Avenue's syntax is simple and readily understood, so do not hesitate to take a look if you are a Basic or Fortran or C programmer: it will make sense.
(I wrote a bunch of routines for testing these procedures, too. For instance, if you jitter a number and immediately try to read the jittered bits, they should equal the bitmap you started with. These routines are available in the ArcView Steganography extension package.)
The heart of the code (SetBits and GetBits) requires only basic arithmetic operations: comparison, addition, subtraction, multiplication, exponentiation, base-2 logarithm, floor, and ceiling. Programming environments without floor and ceiling can use truncation or rounding. Even the base-2 logarithm can be dispensed with at some cost in execution time: it is used only to get a good starting estimate of the correct exponent. (If you do not have base-2 logarithm, but have another one--base-10 and natural logs are frequently available--use the identity log2(x) = log(x)/log(2) where "log" stands for the logarithm to any base.)
These algorithms can readily be adapted to jitter integers. You don't have to pick integers apart into a mantissa and an exponent. The integer has no exponent and acts like a pure mantissa.
--William A. Huber, Spring 2002
