1 // JIFFEE - JavaScript Interactive Fiction Framework for Education and Entertainment
  2 // Copyright (c) 2008 by Michael S. Kenniston.  All rights reserved.
  3 // Full documentation is at http://jiffeegames.com
  4 
  5 // jiffee-encoding.js
  6 
  7 // set up a proper namespace to avoid naming conflicts
  8 var com;
  9 if (!com) {com = {};}
 10 if (!com.jiffeegames) {com.jiffeegames = {};}
 11 
 12 /**
 13 Create an empty Encoding object.  The normal call is
 14 <pre>
 15 var encoding = new com.jiffeegames.Encoding();
 16 </pre>
 17 @constructor
 18 @requires com.jiffeegames.Checks
 19 @class An Encoding object very efficiently encodes the entire state
 20 of the game as a string, or decodes it from a string.
 21 The model used is very general, so there should be no need to change this
 22 code for any specific game.  It basically takes the whole string and 
 23 breaks it up into 4-char 'chunks', each of which is interpreted
 24 as a base-90 integer.  Each of these integers in turn is interpreted as a
 25 mixed-base integer, where each 'place' stores the value of one variable.
 26 Note that "variable" here means a named value being stored in the encoding,
 27 which is not the same as a JavaScript "var".
 28 <br><br>
 29 The model:
 30 <br><br>
 31 The state is divided into 'chunks', each of which is a roughly 26-bit
 32 integer which holds the encoded value of one or more variables.
 33 Each chunk has both a 'chunkAsNum' and a 'chunkAsStr' which both hold the
 34 same number and are kept in sync.
 35 <br>
 36 The chunkAsStr is just a base-90 representation of the integer.
 37 <br>
 38 The chunkAsNum is the same value, but stored as a 64-bit JavaScript
 39 floating point number.
 40 <br>
 41 The integer represents the variable values in mixed-base format, e.g. if:
 42 <ul>
 43 <li>variable #0 ranges from 0-6
 44 <li>variable #1 from 0-2
 45 <li>variable #2 from 0-100
 46 </ul>
 47 then:
 48 <ul>
 49 <li>variable #0 is in the 'one's' place
 50 <li>variable #1 is in the 'seven's' place
 51 <li>variable #2 is in the 'twenty-one's' place (7*3)
 52 </ul>
 53 This scheme maximizes the amount of information you can represent in the
 54 string, which is restricted to printable characters and thus has only about
 55 6.5 bits per byte available for real data.  We stick to ASCII characters,
 56 because Unicode would have even worse efficiency once the UTF-8 encoding
 57 rules are taken into account.  (This deliberately reflects the limitations
 58 of cookies, so that these strings may easily be stored inside a cookie.)
 59 <br><br>
 60 This means that the state of each variable in the game is stored in multiple
 61 places, all of which are kept synchronized:
 62 <ul>
 63 <li>this.chunkAsStr_, an array of 4-char strings, one per chunk
 64 <li>this.chunkAsNum_, an array of JavaScript numbers, one per chunk
 65 <li>this.value_, the individual variable values
 66 </ul>
 67 Of course the variable values are also stored on disk (in cookies) and
 68 in the jiffee state-management code, but that is outside the scope of this file.
 69 <br><br>
 70 The standard index names used are:
 71 <ul>
 72 <li>chunkNum, the index of a chunk
 73 <li>varNum, the index of a variable in this.value_, this.range_
 74 </ul>
 75 */
 76 
 77 com.jiffeegames.Encoding =
 78   function Encoding() {
 79     com.jiffeegames.Checks.validate(arguments);
 80   };
 81 
 82 com.jiffeegames.Encoding.prototype.IMPLEMENTS = 'com.jiffeegames.Encoding';
 83 com.jiffeegames.Encoding.prototype.USES = [
 84     'com.jiffeegames.Cookies'
 85     ];
 86 
 87 com.jiffeegames.Encoding.prototype.init =
 88   function init(locate, language) {
 89     var checks = com.jiffeegames.Checks;
 90     var encoding = this;
 91     checks.validate(arguments);
 92     var cookies = locate('com.jiffeegames.Cookies');
 93 
 94 /**
 95 Do an integer division.
 96 @param {integer} a The dividend.
 97 @param {integer} b The divisor.
 98 @returns The quotient, truncated to an integer.
 99 @type integer
100 */
101 
102 com.jiffeegames.Encoding.prototype.integerDivide_ =
103   function integerDivide_(a, b) {
104     return (a / b) | 0;  // force 32-bit int rep to fake integer division
105   };
106 
107 /**
108 Add another variable to the encoding.  Note that the noun and trait names
109 are used only to compute a fingerprint for the encoding;
110 they are not actually stored anywhere.
111 @param {String} noun The name of the noun which owns the trait.
112 @param {String} trait The name of the trait whose value is being encoded.
113 @param {integer} maxVal The maximum allowed value of the trait.
114 @returns The index of the new variable within the Encoding.
115 This index must be used to refer to the variable in get/set calls.
116 @type integer
117 */
118 
119 com.jiffeegames.Encoding.prototype.addVar =
120   function addVar(noun, trait, maxVal) {
121     checks.validate(arguments);
122     if (maxVal < 1) {
123       checks.error(arguments, 'J007', 'smallest allowable maximum is 1');
124     }
125     if (maxVal >= this.maxRange_) {
126       checks.error(arguments, 'J008',
127                   'largest allowable maximum is ' + (this.maxRange_-1));
128     }
129     if (this.isStarted_) {
130       checks.error(arguments, 'J009', 'called after chunks were built');
131     }
132 
133     var varNum = this.value_.length;
134     this.range_.push(maxVal + 1);  // number of values is max+1 to include zero
135     this.value_.push(0);
136 
137     // Accumulate a string descriptor, which is converted into a SHA-224 hash
138     // once we're done.  The provides protection against a game trying to
139     // restore state from a different game, or from an obsolete cookie
140     // from an old version of the same game.
141 
142     this.fingerprint_.push(noun);
143     this.fingerprint_.push(trait);
144     this.fingerprint_.push(maxVal);
145 
146     return varNum; // use this number to refer to this variable in the future
147   };
148 
149 /**
150 Allocate all the variables to "chunks".
151 Do this after adding all variables but before touching the encodingString.
152 This is not a normal start() routine because it needs to be called *after*
153 traits starts.
154 @type void
155 */
156 
157 com.jiffeegames.Encoding.prototype.startManually =
158   function startManually() {
159     checks.validate(arguments);
160     if (this.isStarted_) {
161       checks.error(arguments, 'J010', 'tried to build chunks twice.');
162     }
163 
164     this.chunkAsNum_ = [];          // map chunkNum to int
165     this.chunkAsStr_ = [];          // map chunkNum to string
166     this.varsInChunk_ = [];         // map chunkNum to list of varNum
167     this.chunkNumFromVarNum_ = [];  // map varNum to chunkNum
168 
169     // Sort variables, biggest first, then do a first-fit into chunkAsNum.
170     // This does not guarantee optimum packing, but it does make the 'maximum
171     // amount of state that will fit' less sensitive to trivial
172     // changes in a game.
173 
174     var tlist = [];
175     var vlen = this.value_.length;
176     for (var vdex = 0; vdex < vlen; vdex++) {
177       tlist.push(vdex);
178     }
179     var enc = this; // for closure of 'sorter' function
180     var sorter = function(a, b) {
181       var res = enc.range_[b] - enc.range_[a];
182       if (res !== 0) {
183         return res;
184       }
185       return a - b;  // make this a stable sort, to simplify testing
186     };
187     tlist.sort(sorter);
188 
189     var remains = [];
190     var tlen = tlist.length;
191     var varNum;
192     for (var tdex = 0; tdex < tlen; tdex++) {
193       varNum = tlist[tdex];
194       var r = this.range_[varNum];
195       // look for an existing chunk with enough room for this variable
196       var chunkNum;
197       var nChunks = remains.length;
198       for (chunkNum = 0; chunkNum < nChunks; chunkNum++) {
199         if (r <= remains[chunkNum]) {
200           break;
201         }
202       }
203       if (chunkNum === this.varsInChunk_.length) {
204         // no room, so create a new empty chunk
205         remains.push(this.maxRange_);
206         this.chunkAsNum_.push(0);
207         this.chunkAsStr_.push('aaaa');
208         this.varsInChunk_.push([]);
209       }
210 
211       // finally, assign the variable to a chunk
212       this.varsInChunk_[chunkNum].push(varNum);
213       this.chunkNumFromVarNum_[varNum] = chunkNum;
214       remains[chunkNum] = this.integerDivide_(remains[chunkNum], r);
215     }
216 
217     // now that chunks are built, prevent any more variables from being added
218     this.isStarted_ = true;
219 
220     // some variables may have had values set before chunks were built,
221     // so set them all now to initialize c.chunkAsStr and c.chunkAsNum
222     vlen = this.value_.length;
223     for (varNum = 0; varNum < vlen; varNum++) {
224       var newVal = this.value_[varNum];
225       if (newVal !== 0 ) {
226         this.setVar(varNum, newVal);
227       }
228     }
229 
230     // Compute fingerprint, based on names of all noun/trait/maxval values.
231     var shaObj = new jsSHA(this.fingerprint_.join('/'));
232     // If the fingerprint algorithm changes, change this to invalidate
233     // any existing (and thus obsolete) cookies in players' browsers.
234     var fpVersion = 'A';
235     this.fingerprint_ = shaObj.getHash('SHA-224', 'HEX') + fpVersion;
236   };
237 
238 /**
239 Get the hash code (fingerprint) associated with this encoding.
240 @returns The fingerprint.
241 @type String
242 */
243 
244 com.jiffeegames.Encoding.prototype.getFingerprint =
245   function getFingerprint() {
246     checks.validate(arguments);
247     if (!this.isStarted_) {
248       checks.error(arguments, 'J011', 'called before chunks were built');
249     }
250     return this.fingerprint_;
251   };
252 
253 /**
254 Get the string that encodes the entire game state.
255 @returns The string that encodes the state.
256 @type String
257 */
258 
259 com.jiffeegames.Encoding.prototype.getString =
260   function getString() {
261     checks.validate(arguments);
262     if (! this.isStarted_) {
263       checks.error(arguments, 'J012', 'called before chunks were built');
264     }
265     return this.chunkAsStr_.join('');
266   };
267 
268 /**
269 Change the state of the whole game as needed to match an encoded string.
270 @param {String} str The string that encodes a state.
271 @type void
272 */
273 
274 com.jiffeegames.Encoding.prototype.setString =
275   function setString(str) {
276     checks.validate(arguments);
277     if (! this.isStarted_) {
278       checks.error(arguments, 'J013', 'called before chunks were built');
279     }
280     if (typeof str !== 'string') {
281       checks.error(arguments, 'J074', 'argument must be a string');
282     }
283     if (str.length !== 4 * this.chunkAsNum_.length) {
284       checks.error(arguments,
285                    'J014',
286                    'string should have length ' +
287                        (4 * this.chunkAsStr_.length) +
288                        ' but had length ' + str.length);
289     }
290 
291     var clen = this.chunkAsNum_.length;
292     for (var chunkNum = 0; chunkNum < clen; chunkNum++) {
293       // split and store string representation
294       var ss = str.substr(4*chunkNum, 4);
295       this.chunkAsStr_[chunkNum] = ss;
296 
297       // make chunkAsNum match chunkAsStr
298       var n = this.intFromChar_[ss.charAt(0)];
299       n = n * this.base_ + this.intFromChar_[ss.charAt(1)];
300       n = n * this.base_ + this.intFromChar_[ss.charAt(2)];
301       n = n * this.base_ + this.intFromChar_[ss.charAt(3)];
302       this.chunkAsNum_[chunkNum] = n;
303 
304       // make value match chunkAsNum
305       var tlist = this.varsInChunk_[chunkNum];
306       for (var tdex = tlist.length - 1; tdex >= 0; tdex--) {
307         var varNum = tlist[tdex];
308         this.value_[varNum] = n % this.range_[varNum];
309         n = this.integerDivide_(n, this.range_[varNum]);
310       }
311     }
312   };
313 
314 /**
315 Set the value of a single variable in the Encoding.
316 @param {integer} varNum The index of the variable in the encoding.
317 @param {integer} newVal The new value of the variable.
318 @type void
319 */
320 
321 com.jiffeegames.Encoding.prototype.setVar =
322   function setVar(varNum, newVal) {
323     checks.validate(arguments);
324     if (varNum < 0 || varNum >= this.value_.length) {
325       checks.error(arguments, 'J016', 'illegal varNum');
326     }
327     if (newVal < 0) {
328       checks.error(arguments, 'J017', 'smallest allowed value is zero');
329     }
330     if (newVal >= this.range_[varNum]) {
331       checks.error(arguments,
332                   'J018',
333                   'largest allowed value is ' + (this.range_[varNum] - 1));
334     }
335 
336     this.value_[varNum] = newVal;
337     if (! this.isStarted_) {
338       return;
339     }
340 
341     // make c.chunkAsNum match c.value_
342     // for simplicity, just re-encode the whole int
343     var chunkNum = this.chunkNumFromVarNum_[varNum];
344     var n = 0;
345     var tlist = this.varsInChunk_[chunkNum];
346     var tlen = tlist.length;
347     for (var tdex = 0; tdex < tlen; tdex++) {
348       n = n * this.range_[tlist[tdex]] + this.value_[tlist[tdex]];
349     }
350     this.chunkAsNum_[chunkNum] = n;
351 
352     // make c.chunkAsStr match c.chunkAsNum
353     var c3 = this.charFromInt_.charAt(n % this.base_);
354     n = this.integerDivide_(n, this.base_);
355     var c2 = this.charFromInt_.charAt(n % this.base_);
356     n = this.integerDivide_(n, this.base_);
357     var c1 = this.charFromInt_.charAt(n % this.base_);
358     n = this.integerDivide_(n, this.base_);
359     var c0 = this.charFromInt_.charAt(n);
360     this.chunkAsStr_[chunkNum] = c0 + c1 + c2 + c3;
361   };
362 
363 /**
364 Read the value of a single encoded variable.
365 @param {integer} varNum The index of the variable within an Encoding.
366 @returns The value of the variable.
367 @type integer
368 */
369 
370 com.jiffeegames.Encoding.prototype.getVar =
371   function getVar(varNum) {
372     checks.validate(arguments);
373     if (varNum < 0 || varNum >= this.value_.length) {
374       checks.error(arguments, 'J019', 'illegal varNum');
375     }
376 
377     return this.value_[varNum];
378   };
379 
380 // contination of init()
381 
382     this.charFromInt_ = cookies.legalChars();
383     this.base_ = this.charFromInt_.length;
384     this.maxRange_ = this.base_ * this.base_ *
385                       this.base_ * this.base_;
386     this.intFromChar_ = {};
387     for (var codePoint = 0; codePoint < this.base_; codePoint++) {
388       this.intFromChar_[this.charFromInt_.charAt(codePoint)] = codePoint;
389     }
390     this.range_ = [];  // index by varNum
391     this.value_ = [];  // index by varNum
392     this.isStarted_ = false;
393     this.fingerprint_ = [];
394   };
395 
396