1. A feeble encyption system
For this assignment, you are to implement a simple text scrambler. The input is a sequence of upper-case characters 'A' through 'Z', supplied on stdin terminated by a newline. The scrambler works by applying a repeatedly applying a simple scrambling step.
2. The basic scrambling step
Imagine that the input sequence is written on cards, one character per card, with the first character at the front of the deck. A scrambling step consists of (a) removing the front card from the deck; (b) moving the k following cards from the front to the back of the deck, one at a time, where k is 1 if the top card was A, 2 for B, 3 for C, etc. up to 26 for Z; (c) replacing the original front card removed in step (a) on the back of the deck.
For example, if the input is ABCDEFG, one scrambling step removes A, moves B (one card) the the end, and re-appends A, giving CDEFGBA. Applying the scrambling step a second time removes C, moves DEF (three cards) to the end, and re-appends C, giving GBADEFC.
If the number of cards to move is more than the number of cards in the deck, some may be moved more than once. An extreme example is that scrambling ZA moves A from the front to the back of a very short deck 26 times, leaving AZ after Z is re-appended at the end. For a more realistic example, scrambling ZOOLOGIST once gives LOGISTOOZ.
Strings of length 0 or 1 are not affected by the scrambling operation.
3. Your task
You are to write a program scramble that implements both scrambling and its inverse "unscrambling" operation (which you will need to figure out how to do). Your scramble program should take as input a line consisting solely of capital letters terminated by a newline, and apply the basic scrambling step a number of times specified by argv[1]. The result of doing this scrambling should be written to stdout, again terminated by a newline. For example:
$ echo ZOOLOGIST | ./scramble 10000 LZTIOOSOG $
With a negative argument -N, scramble should perform the inverse operation N times. So the pipe "scramble 999 | scramble -999" should copy its input to its output intact. Calling scramble with an argument of zero should likewise pass the input to the output unmodified.
4. Details
Your program is not required to deal with non-standard inputs. You may assume that the only inputs it receives consist of a single line of only capital letters. However, you should design it to deal with arbitrarily long lines.
5. Submitting your program
Submit your program as usual using the /c/cs223/bin/submit script. You may either submit a single file scramble.c or multiple files together with a Makefile that generates scramble when called with make scramble.
6. Sample solution
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <assert.h>
5
6 /* read a line of text from stdin
7 * and return it (without terminating newline) as a freshly-malloc'd block.
8 * Caller is responsible for freeing this block.
9 * Returns 0 on error or EOF.
10 * (copied from hw2 sample solutions) */
11 char *
12 getline(void)
13 {
14 char *line; /* line buffer */
15 int n; /* characters read */
16 int size; /* size of line buffer */
17 int c;
18
19 size = 1;
20 line = malloc(size);
21 if(line == 0) return 0;
22
23 n = 0;
24
25 while((c = getchar()) != '\n' && c != EOF) {
26 while(n >= size - 1) {
27 size *= 2;
28 line = realloc(line, size);
29 if(line == 0) return 0;
30 }
31 line[n++] = c;
32 }
33
34 if(c == EOF && n == 0) {
35 /* got nothing */
36 free(line);
37 return 0;
38 } else {
39 line[n++] = '\0';
40 return line;
41 }
42 }
43
44 /* reverse a malloc'd null-terminated string */
45 /* returns a new malloc'd string and frees its argument */
46 char *
47 rev(char *s)
48 {
49 char *s2;
50
51 int i;
52 int len;
53
54 len = strlen(s);
55
56 s2 = malloc(len+1);
57 assert(s2 != 0);
58
59 for(i = 0; i < len; i++) {
60 s2[i] = s[len-i-1];
61 }
62
63 s2[len] = '\0';
64
65 free(s);
66
67 return s2;
68 }
69
70
71
72 /* various constants for scramble */
73 #define BASE_CHARACTER ('A')
74 #define MAX_CHARACTER ('Z')
75 #define SPARE_ROOM (MAX_CHARACTER - BASE_CHARACTER + 2)
76
77 /* this must be at least twice len + SPARE_ROOM */
78 /* to avoid overlaps in memcpy */
79 #define BufSize(len) (2*(len)+1024)
80
81 /* scrambler */
82 /* first argument is a malloc'd null-terminated string */
83 /* This string will be freed by this routine. */
84 /* second argument is number of times to apply the scrambling operation */
85 /* return value is a new malloc'd null-terminated string */
86 char *
87 scramble(char *input, int n)
88 {
89 /* basic idea: we'll allocate a buffer somewhat bigger
90 * than the input, roll the scrambled string along the
91 * buffer, and move it back to the start if it gets too
92 * close to the end */
93 int len; /* length of input */
94 int buflen; /* length of buffer */
95 char *buf; /* buffer */
96
97 char *top; /* first character in string */
98 char *bottom; /* first position after string */
99
100 char card; /* top of deck character */
101 int count; /* how many characters to move */
102
103 int i; /* how many times we've scrambled */
104
105 assert(input != 0);
106
107 /* set up buffer and pointers */
108 len = strlen(input);
109
110 /* special case: 1 or 0 characters have no effect */
111 if(len <= 1) return input;
112
113 /* otherwise build the buffer */
114 buflen = BufSize(len);
115 buf = realloc(input, buflen);
116 assert(buf != 0);
117
118 top = buf;
119 bottom = top + len;
120
121 for(i = 0; i < n; i++) {
122 /* make sure there is enough room */
123 if((buf + buflen) - bottom < SPARE_ROOM) {
124 /* shift back to start */
125 memcpy(buf, top, len);
126 top = buf;
127 bottom = top + len;
128 }
129
130 /* grab top card and compute count */
131 card = *top++;
132
133 /* take remainder to avoid recopying short strings */
134 assert(BASE_CHARACTER <= card);
135 assert(card <= MAX_CHARACTER);
136 count = (card - BASE_CHARACTER + 1) % (len - 1);
137
138 /* using memcpy here is slightly faster than doing it by hand */
139 memcpy(bottom, top, count);
140 top += count;
141 bottom += count;
142
143 /* restore former top card */
144 *bottom++ = card;
145
146 assert(bottom - top == len);
147 }
148
149 /* copy to base of buffer again */
150 /* note we use memmove because we aren't sure of no overlap */
151 memmove(buf, top, len);
152
153 /* tack on the missing null terminator */
154 buf[len] = '\0';
155
156 /* shrink and return */
157 return realloc(buf, len+1);
158 }
159
160 int
161 main(int argc, char **argv)
162 {
163 char *s;
164 int n;
165
166 if(argc != 2) {
167 fprintf(stderr, "Usage: %s scramble-count\n", argv[0]);
168 exit(1);
169 }
170
171 n = atoi(argv[1]);
172
173 s = getline();
174
175 if(n < 0) {
176 s = rev(scramble(rev(s), -n));
177 } else {
178 s = scramble(s, n);
179 }
180
181 puts(s);
182
183 free(s);
184
185 return 0;
186 }