LFSR And Encryption: TOY

[an error occurred while processing this directive]

CIS 110

LFSR and Encryption in TOY

Programming Assignment

(US Army photo from ARL Technical Library)

Goals
Submission
Background
Before You Begin
Your Program
Part I: LFSR
Part II: Reading and Encrypting One Bit
Part III: Encrypting All Bits
Part IV: Encrypting Images
Procedure for Developing a TOY Program
Debugging
Frequently Asked Questions

Goals

Learn about programming in a low-level machine language.
To gain a better understanding of how variables are stored and manipulated in the computer.
Learn to apply the concepts learned through Java to another programming language. Compare LFSR in Java and in TOY.
To appreciate the programming and debugging advantages of a structured programming language like Java over machine language!
Get familiar with hexadecimal number system.
Use the pipe operator to redirect outputs of one program to the input of another.

Submission

Submit encryption.toy and a completed readme_encryption_toy.txt file using the submission link in the sidebar.

In the old days of Computer Science, high-level langugages like Java did not exist yet. Programming started with bits. You are probably thinking, 0s and 1s, but did you know that they didn't even have 1s in the beginning? Punch cards were used to write and compile a computer program, in binary! The next higher level from binary is hexadecimal, which is a base-16 number system. TOY is a mock-up machine language with hexadecimal syntax and Assembly language in the comments. Assembly languages are associated with the chip architecture on a computer or phone and used by low-level system programmers. Only after that do you arrive at high-level human readable programming languages like Java. However, computers cannot read high-level languages, and they have to be translated down to machine code.

Practicing to write programs in TOY will help you understand what goes on under the hood of software programs, which usually compile into machine code for execution. The syntax in TOY is very close to machine code that the computer actually reads.

In this assignment, you will be doing conceptually the same thing as the previous homework, however, now in TOY instead of Java.

Before You Begin

Development Environment

We strongly recommend developing in Visual X-TOY 7.3.
This version is newer than the version on the booksite, and includes improved auto-commenting features that will likely save you a very significant amount of time over older X-TOY versions. You will need to use TOY.java for final testing of the image encryption and decryption, but you will be able to write all your code and do nearly all your testing within X-TOY. Unless you are a masochist, do not test your program with TOY.java until you are sure it is encrypting and decrypting test input correctly within X-TOY. To specify the standard input to use when testing in X-TOY, click Open... on the StdIn pane or enter values manually into the entry box.
Download and compile the command line TOY simulator TOY.java. You will need this encrypting and decrypting images. It is essential that you use this version of the TOY simulator rather than the version on the booksite. They differ in the way they print debug information, and the booksite version will not work for this assignment.
You may need StdIn.java and In.java, if you are working on the lab computers or set up DrJava manually on your computer.

Your Program

You will extend on the skeleton program (provided) encryption.toy to:

Produces pseudo-random bits by simulating a linear feedback shift register, and encrypt data in TOY;
Reads from StdIn the seed, tap position, and the data;
Stores the seed in a register and uses the <<, >> and & operators to manipulate it (Review Homework 4 and Lecture 7 for a description of LFSRs and encryption);
Prints the encrypted results to StdOut.

Conceptually, the provided ImageToTOY and TOYToImage serve the same purpose as the ImageData class from Homework 4, and you are writing a TOY program encryption.toy that combines the functionality of LFSR init(), step(), generate(), and PhotoMagic.transform() into one program.

At the end of this page, you will find a list of procedure steps to develop a TOY program, some debugging tips, and a collection of FAQs.

Warning Debugging machine language is extremely tricky, no matter how much experience you have. It is imperative to be able to carefully proofread your code numerous times, which means working in shorter stints over a period of days. So start early, and don't wait to come to TA office hours!

Part I: Reading in the Header

Programming and debugging in TOY is even more finicky than Java, so it is essential to write and test your code in very small steps. The first step is to understand the input file format, read in everything but the actual data, and print it back out. This part is the equivalent of LFSR.init().

Required Files

Download the encryption.toy skeleton to get started, and the readme_encryption_toy.txt template.
zeros.in is a simple input file for encryption.toy that you can use for tests.

Input Format

The TOY simulator represents data in text format. Each TOY word is 4 hex digits, with white space separating successive words. Your program should read standard input in the following format (you do not need to do any error checking):

The first word of standard input is the number of bits in the seed. Save this value in a register, and also print it out. Document the register you chose in your register map.
The second word is the seed, which will be at most 16 bits long. Save it in a register, and print it out. Document your register choice in the register map.
The third word as the tap bit. Save this in a register too, print it out, and document your register choice.
The next two words are unencrypted data that should be printed to standard output unchanged. We will use these two numbers to store the image's width and height, so they should not get encrypted. You should read them and print them back out, but you will never need to use the values again. Instead of attributing registers just to these values, you can set aside some registers in your register map as "scratch registers" for intermediate computations, and use them to read in and write out these values.
All subsequent words (except the last one) are the actual data to be encrypted. For your convenience each bit of data is transmitted as an entire word (0000 or 0001), instead of packing 16 bits of data into each word. Do not read in this data yet. First make sure you can read in and print out the five words described above.
The last word of input is FFFF. TOY has no facility for detecting the end of the input, so the final FFFF serves this purpose. (C and C++ using a similar mechanism to indicate the end of strings.) Do not read in this data yet. First make sure you can read in and print out the five words described above.

Output Format

Your program should output data in exactly the same format as the input. Print out the number of bits, seed, tap position, and following two words unchanged. In later steps you will print out all the encrypted data and the final FFFF. So far, your program's output should stop before the encrypted data.

Recall that you access StdIn by loading from mem[FF] and you access StdOut by storing to mem[FF].

For example, the input file zeros.in is a valid input to encryption.toy specifying the 11-bit (000B in hex) seed 01101000010 (0342 in hex), tap bit 8, two arbitrary words (we picked DEAD and BEEF in hex for this file, see this page for an explanation), and a series of 8 0-bits.:

Your program should ultimately produce a file zeros.out with the following contents. For now, you should only be printing the first six words.

Using the command (in the Terminal/Command Prompt, not in DrJava):

% java TOY encryption.toy < zeros.in > zeros.out

Observe that the output of encryption.toy is itself valid input to encryption.toy. This means that you can run the encrypted ouput back through encryption.toy to decrypt it. You can feed the output of one program into another program as input using a pipe in the terminal. Like input and output redirection, pipes do not work in DrJava:

% java TOY encryption.toy < zeros.in | java TOY encryption.toy > zeros.out2

uses the file zeros.in as the standard input to encryption.toy, and feeds the output into another run of encryption.toy. The output of the second run is saved to the file zeros.out2, which should be indentical to zeros.in if your program works correctly. The pipe character | is the same vertical bar that Java uses for the or operator (||).

Part II: Reading and Encrypting One Bit

Once you are successfully reading in and printout out the header (number of bits in seed, seed, tap, and two unencrypted words), read in and encrypt a single bit:

Read in one word from standard input (containing one bit of actual data). Document the register you use for this in your register map.
Generate a single random bit (the equivalent of LFSR.step()). You will need to extract individual bits from your seed register to XOR. You will find the left shift (<<), right shift (>>), and and (&) operators useful to do this.
Encrypt the bit your read in by XOR-ing it with the random bit you generated, and print it out. Now your output from encrypting zeros.in should include the first encrypted bit after the header.
Don't forget to comment your code, and to document any registers you use in your register map.

Part III: Encrypting All Bits

The final step of your TOY program is reading in and encrypting all bits. This is roughly equivalent to PhotoMagic.transform().

Add a loop around your code to encrypt a single bit. The loop should stop if the bit you read is FFFF. Hint: You may need several instruction to set up a condition you can check with one of TOY's two branch instructions.
You will probably need to renumber some of your encryption code because you will be inserting code for the while loop before it. If you add or remove instructions after you've written your branch instructions, you may need to update the branch targets too. This is one of the most tedious, error-prone, and unpleasant aspects of programming in machine language.
Write FFFF to standard output at the end of the loop. Your output for zeros.in should now match the zeros.out listed above.
Don't forget to comment your code and update your register map.
Test your program with more complicated test files than zeros.in. In addition to working out the correct solution by hand, you can easily update the main function in your Java LFSR implementation to encrypt a series of bits just like encryption.toy so you can compare output. You can also compare the output of your program with other students' output.

Part IV: Encrypting Images

Required Files

For encrypting and decrypting images, you will need ImageToTOY.java, TOYToImage.java, and ImageData.java.
You may need Picture.java, if you are working on the lab computers or set up DrJava manually on your computer.
white-10x10.png is a 10x10 white image that is also useful for testing. In addition, you should develop your own test input files and share them with each other.
TOYXpipe.png is a copy of the pipe image from the previous LFSR homework encrypted with the seed 01101000010 and tap position 8. Be aware that encrypting and decrypting images in TOY will be very slow, so it is best to debug with very small images and test input files like zeros.in and white-10x10.png.

If you're lucky, you will not need to write or modify any code at all for this part. Your existing TOY program should "just work" for images. You will, however, be testing your program much more intensively, and may discover bugs along the way.

Unlike Java, TOY does not come with a facility for reading in Images. You could write a program to do so, but it would be unpleasant. Instead, we provide the Java programs ImageToTOY and TOYToImage to convert image files to input for encryption.toy and convert the output back into an image. The two TOY words that are passed from input to output without modification are used to store the image width and height.

Using pipe operators and the supplied ImageToTOY and TOYToImage programs, you will be able to encrypt and decrypt images. (In the end, you should be able to encrypt images using PhotoMagic, then decrypt them with you TOY program, and vice versa.)

For example,

% java ImageToTOY white-10x10.png 01101000010 8 > white.in

creates a valid input file to encryption.toy from the 10x10 white square white-10x10.png and specifies the seed 01101000010 with tap bit 8.

% java TOYToImage < white.in

reads the contents of white.in from standard input, converts it back to an image, and displays it.

You can chain these together with the actual encryption using pipes:

% java ImageToTOY white-10x10.png 01101000010 8 | java TOY encryption.toy | java TOYToImage

This converts the image white-10x10.png along with the seed and tap into an appropriate input file, runs it through encryption.toy, and converts the output into an encrypted image. Although this works with any image, keep in mind that it will be very slow normal-size images. It is best to test with very small images like white-10x10.png and artifical test files like zeros.in.

Similarly, you should be able to produce the pipe image with the command:

% java ImageToTOY TOYXpipe.png 01101000010 8 | java TOY encryption.toy | java TOYToImage

Procedure for Developing a TOY Program

To simulate the execution of your program on a TOY machine, use either the bare-bones TOY.java or the full-blown Visual X-TOY simulator. To get started, download the sample TOY program multiply.toy.

Visual X-TOY simulator. The Visual X-TOY simulator from lecture provides lots of useful development features. There are three modes (edit, debug, and machine). Download it from the link on the assignment page.

To load a TOY program, select File -> Open, then browse to find the program, e.g., multiply.toy.
To execute your program, select Mode -> Debug Mode. Then click the Run button at the bottom. You can enter data on standard input by typing the value in the Stdin tab and clicking the Add button. You will have to click theRun button to resume execution. You can see the results on standard output in the Stdout tab.
To edit your own program, select Mode -> Edit Mode. You can type your program directly in the edit window. You might wish to use multiply.toy as a reference for formatting and commenting.
To redirect standard input from a file, select Mode -> Load File to Stdin. You should be able to write and debug your program completely within Visual X-TOY using simple input files like zeros.in before switching to images and the command line.
To auto-comment your program to include the assembly language code, select Tools -> Auto-comment Code.
If the assembly language code is not automatically kept up-to-date with the machine code, select Tools|Options, click Auto-Complete, then check Commenting Auto-completion. If you are using Visual X-TOY 7.2, available on the assignment page, this will update the assembly comments whenever you modify an instruction, and prevent you from changing the assembly comments directly (rather than updating the machine instruction). If you are using Visual X-TOY 7.1 from the booksite, you will need to select Commenting and Un-commenting Auto-completion This auto-completion mode will only add assembly statements when you enter new instructions; it will not update them or prevent you from editing them.

Using Debug Mode in X-TOY Unlike in Java, it is not simple to print out the values of variables in TOY to see what is going on. Instead you will need to use the debug mode in X-TOY. You can access this from the Mode menu, or by clicking the computer icon on the toolbar. (Switch back to edit mode to modify your code.) In debug mode you can step through your program one instruction at a time, and inspect the contents of every register and memory location as you go. You can load a file to use as StdIn on the StdIn pane. Stepping through your program and methodically scrutinizing these values is how you will discover errors in your instructions. Keep in mind the "Sim Mode" is much cooler than debug mode but is much less useful.

Example Program X-TOY contains many sample programs that you can access through "Open Example Program" in the File menu. You may wish to look at "Fast Multiply" and "Multiply with stdin/stdout" in particular since these use many of the same instructions that you will need for encryption.toy.

Command-line TOY simulator. Download the TOY simulator using the link on the assignment page.

Compile it with
```
    % javac TOY.java
    
```
Test it by typing the values in boldface.
```
    % java TOY multiply.toy
    ...
    Terminal
    ---------------------------------------
    0002
    0005
    000A
    ...
    
```
First, you will see a core dump (the contents of the pc, the registers, and main memory) before the computation begins. Then, you will see the results of the computation, where standard input comes from the terminal and standard output goes to the terminal. This TOY program expects you to enter two integers from standard input (in hex); after you do this, you will see their product (in hex) on standard output. Finally you will see a core dump after the computations ends.
The version of TOY on the assignment page prints the core dump in a different way than the version on the booksite so that it will not interfere with the actual program output. Do not use the booksite version of TOY.java! You will not be able to pipe the output to TOYReadImage.
To edit your own program, use a text editor. You can use multiply.toy as a reference for formatting and commenting.

Debugging

Here are some debugging hints that may help you out.

Remember that all values, memory addresses, and arithmetic are in hex. This is by far the most common error. For example, 1A comes after 19.
Don't forget that Register 0 always contains the value 0. You can specify R0 as a destination register in any instruction, but the result will not be stored in R0. Instead it will be silently discarded.
Watch out for jump statements - if you insert a new line of code between existing lines, the location that you want to jump to may change.
Don't confuse the gray line numbers in X-TOY that are purely for cross-referencing warnings and error messages to lines in your file with the hexadecimal memory addresses that start off each TOY instruction. The instruction "10: 1234" means load the hex value 1234 into memory address hex 10 (decimal 16) no matter which line of your file it appears on.
Comment your TOY code. Also, this may sound silly, but don't accidentally update your comments and forget to update the actual code! Using Visual X-TOY 7.2 from the assignment page, rather than version 7.1 from the booksite will help you avoid this pitfall.
All registers are global variables, so be careful.

Frequently Asked Questions

I can't launch the Java Web Start version of the Visual X-TOY simulator on my laptop. Any ideas? The program requires something called Web Start. When you installed Java initially, this was included. However, Windows security patches have been know to break it. If this happens to you, go to java.com and click the Get It Now button.

I can't launch the Java Web Start version of the Visual X-TOY simulator in the Moore 100 labs. Any ideas? The link in this assignment will not work on the Linux machines in the Moore 100 labs. Instead, select the Terminal from the start menu, and type "xtoy". The link in the assignment does work on the Windows machines, but there is also an icon for X-TOY in the Start Menu under the CIS 110 section of the Course Specific Software menu.

How do I format the TOY output? You can't. Just print one integer per line (0000 or 0001).

My program prints out the right answer, but then I get java.lang.NumberFormatException: null. What could be wrong? You are probably trying to read from standard input, even though it is empty. Be sure that your TOY program terminates when it encounters FFFF.

How do I write/comment a .toy file? To initialize a location in memory to have a value, write (on its own line) the index of the memory location (two hex digits), followed by a colon, followed by a space, followed by the value (four hex digits). Anything else on the line is ignored by the TOY simulator and treated as a comment. Any line that does not follow this format is also interpreted as a comment, but you should begin comment lines with "//" as a matter of good style.

TOY.java doesn't read in some of my instructions. Any ideas? Be sure that you follow the required format XX: XXXX. Check for duplicated line numbers and using the letter O instead of the number 0.

How much do I need to comment my TOY code? At a minimum, you should:

Comment each TOY program with your name, login, and recitation. Your header should also describe the purpose of the program, including what it reads from standard input and what it writes to standard output.
Include a register map at the top of your .toy file.
Comment each TOY instruction with its "assembly language" equivalent. Visual X-TOY can do this for you automatically.
Comment each block of code that serves a high-level purpose, e.g., read seed length, seed, and tap bit.
If you're not sure, comment more. Since you can't give descriptive names to registers and memory addresses like you can to variables, assembly is extremely hard to read and debug without thorough comments.

This assignment was created by Benedict Brown.

(US Army photo from ARL Technical Library)

Table of Contents