Write a program that produces random bits by simulating a linear feedback shift register (see Lecture 1), and then use it to implement a simple encode/decode facility for photographs. The purpose of this program is to introduce you to object-oriented programming and to reinforce the message of Lecture 1.

To prepare for doing this program, reread the slides for Lecture 1 (to reacquaint yourself with the basic ideas behind LFSRs), the lecture slides for "Using Data Types" and "Creating Data Types", and pages 316-335 and 370-377 in the text (to learn the basics of object-oriented programming).

LFSR review.  A linear feedback shift register is a cyclic register of bits that performs discrete step operations that

Our LFSR has two parameters: its number of bits N and the tap position t. These two, plus the initial fill (the sequence of bits that initializes the register) determine the sequence of bits it produces.

Simulate a LFSR.  Your first task is to implement a class that simulates the operation of a linear feedback shift register. Your class should implement the following API:

        LFSR(String fill, int t)  // Constructor to create LFSR with the given initial fill
                                  // and the given tap position
    int step()                    // Step one position, return rightmost (new) bit
    int generate(int k)           // Return a new k-bit pseudo-random integer
 String toString()                // Pack the contents of the register into a String

To implement LFSR you need to choose the internal representation (instance variables) and to implement the three methods in the API. These are all interrelated, and there are several possible approaches. For this assignment, we require that you represent the LFSR as an array of int variables, all of which are either 0 or 1. Therefore, the constructor amounts to creating the array and converting the char values in the string to int values for the array (and initializing your other instance variables). The toString() method amounts to building a string by going through the array.

After completing and testing your constructor and toString() method, your first major task is to implement the step() method, which simulates the operation of the LFSR. You will find code in the Lecture 1 slides for this purpose, but do not use that code. It takes time proportional to N to produce a bit: your challenge is to produce a bit in constant time. There are two reasons that we are giving you this challenge: First, a good solution actually involves less code. Second, it is a warmup for a similar task with an even more interesting application in the next assignment. The trick is to move the tap position. Do not actually shift all the bits in the register.

Extracting multiple bits.  Once you have tested the step() method, you are ready to address your second major task: add a method generate() that takes an integer k as argument and returns a k-bit int value obtained by extracting k bits from the LFSR and converting from binary to integer. This task is easy to accomplish with a little arithmetic: initialize a variable to zero and, for each bit extracted, double the variable and add the bit returned by step(). For example, given the bit sequence 1 1 0 0 1 the variable takes the values 1, 3, 6, 12, 25, ending with the binary representation of the bit sequence.

(Note: The generate() method extracts bits from the LFSR by calling the step() method k times.)

A client to encrypt and decrypt images.  Your next task is write a LFSR client PhotoMagic.java that can encrypt images. PhotoMagic should take three command-line arguments, an image name, a binary password (an initial LFSR fill), and a tap number. It should show an encrypted image and save that image in a file named by preprending an X to the given file name. For example, typing

%  java PhotoMagic pipe.png 01101000010100010000 3

inputs the image on the left below and will produce the image on the right.

 pipe.png                                  Xpipe.png

Important notes: The image should be a .png file because that is a lossless format that preserves the precise bits in the colors. Also, it is best to use a password (and LFSR) that is longer than 12 bits because images have a large number of bits and also because our use of fixed tap position (such as 3) per run does not guarantee that the register will cycle through all values for all lengths. You might enjoy experimenting with violating these rules.

Implementing PhotoMagic is the easiest part of this assignment. It can be accomplished by a few additions and changes to Grayscale.java (Program 3.1.4 of the book). For each pixel, extract the red, green, and blue components of the color, in that order, XOR each one with 8 new generated bits, create a new color, and set the pixel to that color.

Now, here's the magic: If you understood Lecture 1, you know that running the same program with the same password on this picture gives back the original image!

%  java PhotoMagic Xpipe.png 01101000010100010000 3

will produce the following result.

 Xpipe.png                                   XXpipe.png

Submission.   Submit the files LFSR.java, PhotoMagic.java, and readme.txt.

Extra Credit 1.  Using a binary password is weak protection (see Extra Credit 2) and inconvenient, so create a PhotoMagicDeluxe.java implementation to take an alphanumeric password. To avoid problems with special characters, use a six-bit code where the ith character in the string

"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" 

Extra Credit 2.  Assume that you know the password has 11 bits and that the tap is 2. Write a program BreakPhotoMagic.java that tries all possible fills and finds the picture. Hint: all but the correct fill will produce pseudo-random colors, so you can count the frequencies of each 8-bit value and pick the fill that results in the frequencies that deviate the most from 128.