internal/offsetmap.cc - external/github.com/CLD2Owners/cld2 - Git at Google

 // Copyright 2013 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 //
 // Author: dsites@google.com (Dick Sites)
 //
 //

 #include "offsetmap.h"

 #include <string.h>                     // for strcmp
 #include <stdio.h>                      // for fprintf, stderr, fclose, etc
 #include <algorithm>                    // for min

 using namespace std;

 namespace CLD2 {

 // Constructor, destructor
 OffsetMap::OffsetMap() {
   Clear();
 }

 OffsetMap::~OffsetMap() {
 }

 // Clear the map
 // After:
 //   next_diff_sub_ is 0
 //   Windows are the a and a' ranges covered by diffs_[next_diff_sub_-1]
 //   which is a fake range of width 0 mapping 0=>0
 void OffsetMap::Clear() {
   diffs_.clear();
   pending_op_ = COPY_OP;
   pending_length_ = 0;
   next_diff_sub_ = 0;
   current_lo_aoffset_ = 0;
   current_hi_aoffset_ = 0;
   current_lo_aprimeoffset_ = 0;
   current_hi_aprimeoffset_ = 0;
   current_diff_ = 0;
   max_aoffset_ = 0;           // Largest seen so far
   max_aprimeoffset_ = 0;      // Largest seen so far
 }

 static inline char OpPart(const char c) {
   return (c >> 6) & 3;
 }
 static inline char LenPart(const char c) {
   return c & 0x3f;
 }

 // Print map to file, for debugging
 void OffsetMap::Printmap(const char* filename) {
   FILE* fout;
   bool needs_close = false;
   if (strcmp(filename, "stdout") == 0) {
     fout = stdout;
   } else if (strcmp(filename, "stderr") == 0) {
     fout = stderr;
   } else {
     fout = fopen(filename, "w");
     needs_close = true;
   }
   if (fout == NULL) {
     fprintf(stderr, "%s did not open\n", filename);
     return;
   }

   Flush();    // Make sure any pending entry gets printed
   fprintf(fout, "Offsetmap: %d bytes\n", static_cast<int>(diffs_.size()));
   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
     fprintf(fout, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
     if ((i % 20) == 19) {fprintf(fout, "\n");}
   }
   fprintf(fout, "\n");
   if (needs_close) {
     fclose(fout);
   }
 }

 // Reset to offset 0
 void OffsetMap::Reset() {
   MaybeFlushAll();

   next_diff_sub_ = 0;
   current_lo_aoffset_ = 0;
   current_hi_aoffset_ = 0;
   current_lo_aprimeoffset_ = 0;
   current_hi_aprimeoffset_ = 0;
   current_diff_ = 0;
 }

 // Add to  mapping from A to A', specifying how many next bytes are
 // identical in A and A'
 void OffsetMap::Copy(int bytes) {
   if (bytes == 0) {return;}
   max_aoffset_ += bytes;           // Largest seen so far
   max_aprimeoffset_ += bytes;      // Largest seen so far
   if (pending_op_ == COPY_OP) {
     pending_length_ += bytes;
   } else {
     Flush();
     pending_op_ = COPY_OP;
     pending_length_ = bytes;
   }
 }

 // Add to mapping from A to A', specifying how many next bytes are
 // inserted in A' while not advancing in A at all
 void OffsetMap::Insert(int bytes){
   if (bytes == 0) {return;}
   max_aprimeoffset_ += bytes;      // Largest seen so far
   if (pending_op_ == INSERT_OP) {
     pending_length_ += bytes;
   } else if ((bytes == 1) &&
              (pending_op_ == DELETE_OP) && (pending_length_ == 1)) {
     // Special-case exactly delete(1) insert(1) +> copy(1);
     // all others backmap inserts to after deletes
     pending_op_ = COPY_OP;
   } else {
     Flush();
     pending_op_ = INSERT_OP;
     pending_length_ = bytes;
   }
 }

 // Add to mapping from A to A', specifying how many next bytes are
 // deleted from A while not advancing in A' at all
 void OffsetMap::Delete(int bytes){
   if (bytes == 0) {return;}
   max_aoffset_ += bytes;           // Largest seen so far
   if (pending_op_ == DELETE_OP) {
     pending_length_ += bytes;
     } else if ((bytes == 1) &&
                (pending_op_ == INSERT_OP) && (pending_length_ == 1)) {
       // Special-case exactly insert(1) delete(1) => copy(1);
       // all others backmap deletes to after insertss
       pending_op_ = COPY_OP;
   } else {
     Flush();
     pending_op_ = DELETE_OP;
     pending_length_ = bytes;
   }
 }

 void OffsetMap::Flush() {
   if (pending_length_ == 0) {
     return;
   }
   // We may be emitting a copy op just after a copy op because +1 -1 cancelled
   // inbetween. If the lengths don't need a prefix byte, combine them
   if ((pending_op_ == COPY_OP) && !diffs_.empty()) {
     char c = diffs_[diffs_.size() - 1];
     MapOp prior_op = static_cast<MapOp>(OpPart(c));
     int prior_len = LenPart(c);
     if ((prior_op == COPY_OP) && ((prior_len + pending_length_) <= 0x3f)) {
       diffs_[diffs_.size() - 1] += pending_length_;
       pending_length_ = 0;
       return;
     }
   }
   if (pending_length_ > 0x3f) {
     bool non_zero_emitted = false;
     for (int shift = 30; shift > 0; shift -= 6) {
       int prefix = (pending_length_ >> shift) & 0x3f;
       if ((prefix > 0) || non_zero_emitted) {
         Emit(PREFIX_OP, prefix);
         non_zero_emitted = true;
       }
     }
   }
   Emit(pending_op_, pending_length_ & 0x3f);
   pending_length_ = 0;
 }


 // Add one more entry to copy one byte off the end, then flush
 void OffsetMap::FlushAll() {
   Copy(1);
   Flush();
 }

 // Flush all if necessary
 void OffsetMap::MaybeFlushAll() {
   if ((0 < pending_length_) || diffs_.empty()) {
     FlushAll();
   }
 }

 // Len may be 0, for example as the low piece of length=64
 void OffsetMap::Emit(MapOp op, int len) {
   char c = (static_cast<char>(op) << 6) | (len & 0x3f);
   diffs_.push_back(c);
 }

 void OffsetMap::DumpString() {
   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
     fprintf(stderr, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
   }
   fprintf(stderr, "\n");

   // Print running table of correspondences
   fprintf(stderr, "       op      A =>  A'     (A forward-maps to A')\n");
   int aoffset = 0;
   int aprimeoffset = 0;
   int length = 0;
   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
     char c = diffs_[i];
     MapOp op = static_cast<MapOp>(OpPart(c));
     int len = LenPart(c);
     length = (length << 6) + len;
     if (op == COPY_OP) {
       aoffset += length;
       aprimeoffset += length;
       length = 0;
     } else if (op == INSERT_OP) {
       aoffset += 0;
       aprimeoffset += length;
       length = 0;
     } else if (op == DELETE_OP) {
       aoffset += length;
       aprimeoffset += 0;
       length = 0;
     } else {              // (op == PREFIX_OP)
       // Do nothing else
     }
     fprintf(stderr, "[%3d] %c%02d %6d %6d%s\n",
             i, "&=+-"[op], len,
             aoffset, aprimeoffset,
             (next_diff_sub_ == i) ? " <==next_diff_sub_" : "");

   }
   fprintf(stderr, "\n");
 }

 void OffsetMap::DumpWindow() {
   fprintf(stderr, "DumpWindow(A => A'): max_aoffset_ = %d, "
                   "max_aprimeoffset_ = %d, next_diff_sub_ = %d<br>\n",
           max_aoffset_, max_aprimeoffset_, next_diff_sub_);
   fprintf(stderr, "A  [%u..%u)\n",
           current_lo_aoffset_, current_hi_aoffset_);
   fprintf(stderr, "A' [%u..%u)\n",
           current_lo_aprimeoffset_, current_hi_aprimeoffset_);
   fprintf(stderr, "  diff = %d\n", current_diff_);
   DumpString();
 }

 //----------------------------------------------------------------------------//
 // The guts of the 2013 design                                                //
 // If there are three ranges a b c in  diffs_, we can be in one of five       //
 // states: LEFT of a, in ranges a b c, or RIGHT of c                          //
 // In each state, there are windows A[Alo..Ahi), A'[A'lo..A'hi) and diffs_    //
 // position next_diff_sub_                                                    //
 // There also are mapping constants max_aoffset_ and max_aprimeoffset_        //
 // If LEFT, Alo=Ahi=0, A'lo=A'hi=0 and next_diff_sub_=0                       //
 // If RIGHT, Alo=Ahi=max_aoffset_, A'lo=A'hi=max_aprimeoffset_ and            //
 //   next_diff_sub_=diffs_.size()                                             //
 // Otherwise, at least one of A[) and A'[) is non-empty and the first bytes   //
 //   correspond to each other. If range i is active, next_diff_sub_ is at     //
 //   the first byte of range i+1. Because of the length-prefix operator,      //
 //   an individual range item in diffs_ may be multiple bytes                 //
 // In all cases aprimeoffset = aoffset + current_diff_                        //
 //   i.e. current_diff_ = aprimeoffset - aoffset                              //
 //                                                                            //
 // In the degenerate case of diffs_.empty(), there are only two states        //
 //   LEFT and RIGHT and the mapping is the identity mapping.                  //
 // The initial state is LEFT.                                                 //
 // It is an error to move left into LEFT or right into RIGHT, but the code    //
 //   below is robust in these cases.                                          //
 //----------------------------------------------------------------------------//

 void OffsetMap::SetLeft() {
    current_lo_aoffset_ = 0;
    current_hi_aoffset_ = 0;
    current_lo_aprimeoffset_ = 0;
    current_hi_aprimeoffset_ = 0;
    current_diff_ = 0;
    next_diff_sub_ = 0;
 }

 void OffsetMap::SetRight() {
    current_lo_aoffset_ = max_aoffset_;
    current_hi_aoffset_ = max_aoffset_;
    current_lo_aprimeoffset_ = max_aprimeoffset_;
    current_hi_aprimeoffset_ = max_aprimeoffset_;
    current_diff_ = max_aprimeoffset_ - max_aoffset_;
    next_diff_sub_ = 0;
 }

 // Back up over previous range, 1..5 bytes
 // Return subscript at the beginning of that. Pins at 0
 int OffsetMap::Backup(int sub) {
   if (sub <= 0) {return 0;}
   --sub;
   while ((0 < sub) &&
          (static_cast<MapOp>(OpPart(diffs_[sub - 1]) == PREFIX_OP))) {
     --sub;
   }
   return sub;
 }

 // Parse next range, 1..5 bytes
 // Return subscript just off the end of that
 int OffsetMap::ParseNext(int sub, MapOp* op, int* length) {
    *op = PREFIX_OP;
    *length = 0;
    char c;
    while ((sub < static_cast<int>(diffs_.size())) && (*op == PREFIX_OP)) {
      c = diffs_[sub++];
      *op = static_cast<MapOp>(OpPart(c));
      int len = LenPart(c);
      *length = (*length << 6) + len;
    }
    // If mal-formed or in RIGHT, this will return with op = PREFIX_OP
    // Mal-formed can include a trailing prefix byte with no following op
    return sub;
 }

 // Parse previous range, 1..5 bytes
 // Return current subscript
 int OffsetMap::ParsePrevious(int sub, MapOp* op, int* length) {
   sub = Backup(sub);
   return ParseNext(sub, op, length);
 }

 // Quick debugging dump; does not parse multi-byte items, so just length & 0x3f
 void OffsetMap::PrintPosition(const char* str) {
   MapOp op = PREFIX_OP;
   int length = 0;
   if ((0 < next_diff_sub_) && (next_diff_sub_ <= static_cast<int>(diffs_.size()))) {
     op = static_cast<MapOp>(OpPart(diffs_[next_diff_sub_ - 1]));
     length = LenPart(diffs_[next_diff_sub_ - 1]);
   }
   fprintf(stderr, "%s[%d] %c%02d = A[%d..%d) ==> A'[%d..%d)\n",
           str,
           next_diff_sub_, "&=+-"[op], length,
           current_lo_aoffset_, current_hi_aoffset_,
           current_lo_aprimeoffset_, current_hi_aprimeoffset_);
 }

 // Move active window one range to the right
 // Return true if move was OK
 bool OffsetMap::MoveRight() {
   // If at last range or RIGHT, set to RIGHT, return error
   if (next_diff_sub_ >= static_cast<int>(diffs_.size())) {
     SetRight();
     return false;
   }
   // Actually OK to move right
   MapOp op;
   int length;
   bool retval = true;
   // If mal-formed or in RIGHT, this will return with op = PREFIX_OP
   next_diff_sub_ = ParseNext(next_diff_sub_, &op, &length);

   current_lo_aoffset_ = current_hi_aoffset_;
   current_lo_aprimeoffset_ = current_hi_aprimeoffset_;
   if (op == COPY_OP) {
     current_hi_aoffset_ = current_lo_aoffset_ + length;
     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
   } else if (op == INSERT_OP) {
     current_hi_aoffset_ = current_lo_aoffset_ + 0;
     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
   } else if (op == DELETE_OP) {
     current_hi_aoffset_ = current_lo_aoffset_ + length;
     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + 0;
   } else {
     SetRight();
     retval = false;
   }
   current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
   return retval;
 }

 // Move active window one range to the left
 // Return true if move was OK
 bool OffsetMap::MoveLeft() {
   // If at first range or LEFT, set to LEFT, return error
   if (next_diff_sub_ <= 0) {
     SetLeft();
     return false;
   }
   // Back up over current active window
   next_diff_sub_ = Backup(next_diff_sub_);
   if (next_diff_sub_ <= 0) {
     SetLeft();
     return false;
   }
   // Actually OK to move left
   MapOp op;
   int length;
   bool retval = true;
   // If mal-formed or in LEFT, this will return with op = PREFIX_OP
   next_diff_sub_ = ParsePrevious(next_diff_sub_, &op, &length);

   current_hi_aoffset_ = current_lo_aoffset_;
   current_hi_aprimeoffset_ = current_lo_aprimeoffset_;
   if (op == COPY_OP) {
     current_lo_aoffset_ = current_hi_aoffset_ - length;
     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
   } else if (op == INSERT_OP) {
     current_lo_aoffset_ = current_hi_aoffset_ - 0;
     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
   } else if (op == DELETE_OP) {
     current_lo_aoffset_ = current_hi_aoffset_ - length;
     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - 0;
   } else {
     SetLeft();
     retval = false;
   }
   current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
   return true;
 }

 // Map an offset in A' to the corresponding offset in A
 int OffsetMap::MapBack(int aprimeoffset){
   MaybeFlushAll();
   if (aprimeoffset < 0) {return 0;}
   if (max_aprimeoffset_ <= aprimeoffset) {
      return (aprimeoffset - max_aprimeoffset_) + max_aoffset_;
   }

   // If current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_,
   // use current mapping, else move window left/right
   bool ok = true;
   while (ok && (aprimeoffset < current_lo_aprimeoffset_)) {
     ok = MoveLeft();
   }
   while (ok && (current_hi_aprimeoffset_ <= aprimeoffset)) {
     ok = MoveRight();
   }
   // So now current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_

   int aoffset = aprimeoffset - current_diff_;
   if (aoffset >= current_hi_aoffset_) {
     // A' is in an insert region, all bytes of which backmap to A=hi_aoffset_
     aoffset = current_hi_aoffset_;
   }
   return aoffset;
 }

 // Map an offset in A to the corresponding offset in A'
 int OffsetMap::MapForward(int aoffset){
   MaybeFlushAll();
   if (aoffset < 0) {return 0;}
   if (max_aoffset_ <= aoffset) {
      return (aoffset - max_aoffset_) + max_aprimeoffset_;
   }

   // If current_lo_aoffset_ <= aoffset < current_hi_aoffset_,
   // use current mapping, else move window left/right
   bool ok = true;
   while (ok && (aoffset < current_lo_aoffset_)) {
     ok = MoveLeft();
   }
   while (ok && (current_hi_aoffset_ <= aoffset)) {
     ok = MoveRight();
   }

   int aprimeoffset = aoffset + current_diff_;
   if (aprimeoffset >= current_hi_aprimeoffset_) {
     // A is in a delete region, all bytes of which map to A'=hi_aprimeoffset_
     aprimeoffset = current_hi_aprimeoffset_;
   }
   return aprimeoffset;
 }


 // static
 bool OffsetMap::CopyInserts(OffsetMap* source, OffsetMap* dest) {
   bool ok = true;
   while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
     ok = source->MoveRight();
     if (source->current_lo_aoffset_ != source->current_hi_aoffset_) {
       return false;
     }
     dest->Insert(
         source->current_hi_aprimeoffset_ - source->current_lo_aprimeoffset_);
   }
   return true;
 }

 // static
 bool OffsetMap::CopyDeletes(OffsetMap* source, OffsetMap* dest) {
   bool ok = true;
   while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
     ok = source->MoveRight();
     if (source->current_lo_aprimeoffset_ != source->current_hi_aprimeoffset_) {
       return false;
     }
     dest->Delete(source->current_hi_aoffset_ - source->current_lo_aoffset_);
   }
   return true;
 }

 // static
 void OffsetMap::ComposeOffsetMap(
     OffsetMap* g, OffsetMap* f, OffsetMap* h) {
   h->Clear();
   f->Reset();
   g->Reset();

   int lo = 0;
   for (;;) {
      // Consume delete operations in f. This moves A without moving
      // A' and A''.
      if (lo >= g->current_hi_aoffset_ && CopyInserts(g, h)) {
        if (lo >= f->current_hi_aprimeoffset_ && CopyDeletes(f, h)) {
           // fprintf(stderr,
           //         "ComposeOffsetMap ERROR, f is longer than g.<br>\n");
        }

        // FlushAll(), called by Reset(), MapForward() or MapBack(), has
        // added an extra COPY_OP to f and g, so this function has
        // composed an extra COPY_OP in h from those. To avoid
        // FlushAll() adds one more extra COPY_OP to h later, dispatch
        // Flush() right now.
        h->Flush();
        return;
      }

      // Consume insert operations in g. This moves A'' without moving A
      // and A'.
      if (lo >= f->current_hi_aprimeoffset_) {
        if (!CopyDeletes(f, h)) {
           // fprintf(stderr,
           //         "ComposeOffsetMap ERROR, g is longer than f.<br>\n");
        }
      }

      // Compose one operation which moves A' from lo to hi.
      int hi = min(f->current_hi_aprimeoffset_, g->current_hi_aoffset_);
      if (f->current_lo_aoffset_ != f->current_hi_aoffset_ &&
          g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
        h->Copy(hi - lo);
      } else if (f->current_lo_aoffset_ != f->current_hi_aoffset_) {
        h->Delete(hi - lo);
      } else if (g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
        h->Insert(hi - lo);
      }

      lo = hi;
   }
 }

 // For testing only -- force a mapping
 void OffsetMap::StuffIt(const string& diffs,
                         int max_aoffset, int max_aprimeoffset) {
   Clear();
   diffs_ = diffs;
   max_aoffset_ = max_aoffset;
   max_aprimeoffset_ = max_aprimeoffset;
 }


 }  // namespace CLD2
	// Copyright 2013 Google Inc. All Rights Reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	//
	// Author: dsites@google.com (Dick Sites)
	//
	//

	#include "offsetmap.h"

	#include <string.h> // for strcmp
	#include <stdio.h> // for fprintf, stderr, fclose, etc
	#include <algorithm> // for min

	using namespace std;

	namespace CLD2 {

	// Constructor, destructor
	OffsetMap::OffsetMap() {
	Clear();
	}

	OffsetMap::~OffsetMap() {
	}

	// Clear the map
	// After:
	// next_diff_sub_ is 0
	// Windows are the a and a' ranges covered by diffs_[next_diff_sub_-1]
	// which is a fake range of width 0 mapping 0=>0
	void OffsetMap::Clear() {
	diffs_.clear();
	pending_op_ = COPY_OP;
	pending_length_ = 0;
	next_diff_sub_ = 0;
	current_lo_aoffset_ = 0;
	current_hi_aoffset_ = 0;
	current_lo_aprimeoffset_ = 0;
	current_hi_aprimeoffset_ = 0;
	current_diff_ = 0;
	max_aoffset_ = 0; // Largest seen so far
	max_aprimeoffset_ = 0; // Largest seen so far
	}

	static inline char OpPart(const char c) {
	return (c >> 6) & 3;
	}
	static inline char LenPart(const char c) {
	return c & 0x3f;
	}

	// Print map to file, for debugging
	void OffsetMap::Printmap(const char* filename) {
	FILE* fout;
	bool needs_close = false;
	if (strcmp(filename, "stdout") == 0) {
	fout = stdout;
	} else if (strcmp(filename, "stderr") == 0) {
	fout = stderr;
	} else {
	fout = fopen(filename, "w");
	needs_close = true;
	}
	if (fout == NULL) {
	fprintf(stderr, "%s did not open\n", filename);
	return;
	}

	Flush(); // Make sure any pending entry gets printed
	fprintf(fout, "Offsetmap: %d bytes\n", static_cast<int>(diffs_.size()));
	for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
	fprintf(fout, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
	if ((i % 20) == 19) {fprintf(fout, "\n");}
	}
	fprintf(fout, "\n");
	if (needs_close) {
	fclose(fout);
	}
	}

	// Reset to offset 0
	void OffsetMap::Reset() {
	MaybeFlushAll();

	next_diff_sub_ = 0;
	current_lo_aoffset_ = 0;
	current_hi_aoffset_ = 0;
	current_lo_aprimeoffset_ = 0;
	current_hi_aprimeoffset_ = 0;
	current_diff_ = 0;
	}

	// Add to mapping from A to A', specifying how many next bytes are
	// identical in A and A'
	void OffsetMap::Copy(int bytes) {
	if (bytes == 0) {return;}
	max_aoffset_ += bytes; // Largest seen so far
	max_aprimeoffset_ += bytes; // Largest seen so far
	if (pending_op_ == COPY_OP) {
	pending_length_ += bytes;
	} else {
	Flush();
	pending_op_ = COPY_OP;
	pending_length_ = bytes;
	}
	}

	// Add to mapping from A to A', specifying how many next bytes are
	// inserted in A' while not advancing in A at all
	void OffsetMap::Insert(int bytes){
	if (bytes == 0) {return;}
	max_aprimeoffset_ += bytes; // Largest seen so far
	if (pending_op_ == INSERT_OP) {
	pending_length_ += bytes;
	} else if ((bytes == 1) &&
	(pending_op_ == DELETE_OP) && (pending_length_ == 1)) {
	// Special-case exactly delete(1) insert(1) +> copy(1);
	// all others backmap inserts to after deletes
	pending_op_ = COPY_OP;
	} else {
	Flush();
	pending_op_ = INSERT_OP;
	pending_length_ = bytes;
	}
	}

	// Add to mapping from A to A', specifying how many next bytes are
	// deleted from A while not advancing in A' at all
	void OffsetMap::Delete(int bytes){
	if (bytes == 0) {return;}
	max_aoffset_ += bytes; // Largest seen so far
	if (pending_op_ == DELETE_OP) {
	pending_length_ += bytes;
	} else if ((bytes == 1) &&
	(pending_op_ == INSERT_OP) && (pending_length_ == 1)) {
	// Special-case exactly insert(1) delete(1) => copy(1);
	// all others backmap deletes to after insertss
	pending_op_ = COPY_OP;
	} else {
	Flush();
	pending_op_ = DELETE_OP;
	pending_length_ = bytes;
	}
	}

	void OffsetMap::Flush() {
	if (pending_length_ == 0) {
	return;
	}
	// We may be emitting a copy op just after a copy op because +1 -1 cancelled
	// inbetween. If the lengths don't need a prefix byte, combine them
	if ((pending_op_ == COPY_OP) && !diffs_.empty()) {
	char c = diffs_[diffs_.size() - 1];
	MapOp prior_op = static_cast<MapOp>(OpPart(c));
	int prior_len = LenPart(c);
	if ((prior_op == COPY_OP) && ((prior_len + pending_length_) <= 0x3f)) {
	diffs_[diffs_.size() - 1] += pending_length_;
	pending_length_ = 0;
	return;
	}
	}
	if (pending_length_ > 0x3f) {
	bool non_zero_emitted = false;
	for (int shift = 30; shift > 0; shift -= 6) {
	int prefix = (pending_length_ >> shift) & 0x3f;
	if ((prefix > 0) \|\| non_zero_emitted) {
	Emit(PREFIX_OP, prefix);
	non_zero_emitted = true;
	}
	}
	}
	Emit(pending_op_, pending_length_ & 0x3f);
	pending_length_ = 0;
	}


	// Add one more entry to copy one byte off the end, then flush
	void OffsetMap::FlushAll() {
	Copy(1);
	Flush();
	}

	// Flush all if necessary
	void OffsetMap::MaybeFlushAll() {
	if ((0 < pending_length_) \|\| diffs_.empty()) {
	FlushAll();
	}
	}

	// Len may be 0, for example as the low piece of length=64
	void OffsetMap::Emit(MapOp op, int len) {
	char c = (static_cast<char>(op) << 6) \| (len & 0x3f);
	diffs_.push_back(c);
	}

	void OffsetMap::DumpString() {
	for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
	fprintf(stderr, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
	}
	fprintf(stderr, "\n");

	// Print running table of correspondences
	fprintf(stderr, " op A => A' (A forward-maps to A')\n");
	int aoffset = 0;
	int aprimeoffset = 0;
	int length = 0;
	for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
	char c = diffs_[i];
	MapOp op = static_cast<MapOp>(OpPart(c));
	int len = LenPart(c);
	length = (length << 6) + len;
	if (op == COPY_OP) {
	aoffset += length;
	aprimeoffset += length;
	length = 0;
	} else if (op == INSERT_OP) {
	aoffset += 0;
	aprimeoffset += length;
	length = 0;
	} else if (op == DELETE_OP) {
	aoffset += length;
	aprimeoffset += 0;
	length = 0;
	} else { // (op == PREFIX_OP)
	// Do nothing else
	}
	fprintf(stderr, "[%3d] %c%02d %6d %6d%s\n",
	i, "&=+-"[op], len,
	aoffset, aprimeoffset,
	(next_diff_sub_ == i) ? " <==next_diff_sub_" : "");

	}
	fprintf(stderr, "\n");
	}

	void OffsetMap::DumpWindow() {
	fprintf(stderr, "DumpWindow(A => A'): max_aoffset_ = %d, "
	"max_aprimeoffset_ = %d, next_diff_sub_ = %d<br>\n",
	max_aoffset_, max_aprimeoffset_, next_diff_sub_);
	fprintf(stderr, "A [%u..%u)\n",
	current_lo_aoffset_, current_hi_aoffset_);
	fprintf(stderr, "A' [%u..%u)\n",
	current_lo_aprimeoffset_, current_hi_aprimeoffset_);
	fprintf(stderr, " diff = %d\n", current_diff_);
	DumpString();
	}

	//----------------------------------------------------------------------------//
	// The guts of the 2013 design //
	// If there are three ranges a b c in diffs_, we can be in one of five //
	// states: LEFT of a, in ranges a b c, or RIGHT of c //
	// In each state, there are windows A[Alo..Ahi), A'[A'lo..A'hi) and diffs_ //
	// position next_diff_sub_ //
	// There also are mapping constants max_aoffset_ and max_aprimeoffset_ //
	// If LEFT, Alo=Ahi=0, A'lo=A'hi=0 and next_diff_sub_=0 //
	// If RIGHT, Alo=Ahi=max_aoffset_, A'lo=A'hi=max_aprimeoffset_ and //
	// next_diff_sub_=diffs_.size() //
	// Otherwise, at least one of A[) and A'[) is non-empty and the first bytes //
	// correspond to each other. If range i is active, next_diff_sub_ is at //
	// the first byte of range i+1. Because of the length-prefix operator, //
	// an individual range item in diffs_ may be multiple bytes //
	// In all cases aprimeoffset = aoffset + current_diff_ //
	// i.e. current_diff_ = aprimeoffset - aoffset //
	// //
	// In the degenerate case of diffs_.empty(), there are only two states //
	// LEFT and RIGHT and the mapping is the identity mapping. //
	// The initial state is LEFT. //
	// It is an error to move left into LEFT or right into RIGHT, but the code //
	// below is robust in these cases. //
	//----------------------------------------------------------------------------//

	void OffsetMap::SetLeft() {
	current_lo_aoffset_ = 0;
	current_hi_aoffset_ = 0;
	current_lo_aprimeoffset_ = 0;
	current_hi_aprimeoffset_ = 0;
	current_diff_ = 0;
	next_diff_sub_ = 0;
	}

	void OffsetMap::SetRight() {
	current_lo_aoffset_ = max_aoffset_;
	current_hi_aoffset_ = max_aoffset_;
	current_lo_aprimeoffset_ = max_aprimeoffset_;
	current_hi_aprimeoffset_ = max_aprimeoffset_;
	current_diff_ = max_aprimeoffset_ - max_aoffset_;
	next_diff_sub_ = 0;
	}

	// Back up over previous range, 1..5 bytes
	// Return subscript at the beginning of that. Pins at 0
	int OffsetMap::Backup(int sub) {
	if (sub <= 0) {return 0;}
	--sub;
	while ((0 < sub) &&
	(static_cast<MapOp>(OpPart(diffs_[sub - 1]) == PREFIX_OP))) {
	--sub;
	}
	return sub;
	}

	// Parse next range, 1..5 bytes
	// Return subscript just off the end of that
	int OffsetMap::ParseNext(int sub, MapOp* op, int* length) {
	*op = PREFIX_OP;
	*length = 0;
	char c;
	while ((sub < static_cast<int>(diffs_.size())) && (*op == PREFIX_OP)) {
	c = diffs_[sub++];
	*op = static_cast<MapOp>(OpPart(c));
	int len = LenPart(c);
	length = (length << 6) + len;
	}
	// If mal-formed or in RIGHT, this will return with op = PREFIX_OP
	// Mal-formed can include a trailing prefix byte with no following op
	return sub;
	}

	// Parse previous range, 1..5 bytes
	// Return current subscript
	int OffsetMap::ParsePrevious(int sub, MapOp* op, int* length) {
	sub = Backup(sub);
	return ParseNext(sub, op, length);
	}

	// Quick debugging dump; does not parse multi-byte items, so just length & 0x3f
	void OffsetMap::PrintPosition(const char* str) {
	MapOp op = PREFIX_OP;
	int length = 0;
	if ((0 < next_diff_sub_) && (next_diff_sub_ <= static_cast<int>(diffs_.size()))) {
	op = static_cast<MapOp>(OpPart(diffs_[next_diff_sub_ - 1]));
	length = LenPart(diffs_[next_diff_sub_ - 1]);
	}
	fprintf(stderr, "%s[%d] %c%02d = A[%d..%d) ==> A'[%d..%d)\n",
	str,
	next_diff_sub_, "&=+-"[op], length,
	current_lo_aoffset_, current_hi_aoffset_,
	current_lo_aprimeoffset_, current_hi_aprimeoffset_);
	}

	// Move active window one range to the right
	// Return true if move was OK
	bool OffsetMap::MoveRight() {
	// If at last range or RIGHT, set to RIGHT, return error
	if (next_diff_sub_ >= static_cast<int>(diffs_.size())) {
	SetRight();
	return false;
	}
	// Actually OK to move right
	MapOp op;
	int length;
	bool retval = true;
	// If mal-formed or in RIGHT, this will return with op = PREFIX_OP
	next_diff_sub_ = ParseNext(next_diff_sub_, &op, &length);

	current_lo_aoffset_ = current_hi_aoffset_;
	current_lo_aprimeoffset_ = current_hi_aprimeoffset_;
	if (op == COPY_OP) {
	current_hi_aoffset_ = current_lo_aoffset_ + length;
	current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
	} else if (op == INSERT_OP) {
	current_hi_aoffset_ = current_lo_aoffset_ + 0;
	current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
	} else if (op == DELETE_OP) {
	current_hi_aoffset_ = current_lo_aoffset_ + length;
	current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + 0;
	} else {
	SetRight();
	retval = false;
	}
	current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
	return retval;
	}

	// Move active window one range to the left
	// Return true if move was OK
	bool OffsetMap::MoveLeft() {
	// If at first range or LEFT, set to LEFT, return error
	if (next_diff_sub_ <= 0) {
	SetLeft();
	return false;
	}
	// Back up over current active window
	next_diff_sub_ = Backup(next_diff_sub_);
	if (next_diff_sub_ <= 0) {
	SetLeft();
	return false;
	}
	// Actually OK to move left
	MapOp op;
	int length;
	bool retval = true;
	// If mal-formed or in LEFT, this will return with op = PREFIX_OP
	next_diff_sub_ = ParsePrevious(next_diff_sub_, &op, &length);

	current_hi_aoffset_ = current_lo_aoffset_;
	current_hi_aprimeoffset_ = current_lo_aprimeoffset_;
	if (op == COPY_OP) {
	current_lo_aoffset_ = current_hi_aoffset_ - length;
	current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
	} else if (op == INSERT_OP) {
	current_lo_aoffset_ = current_hi_aoffset_ - 0;
	current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
	} else if (op == DELETE_OP) {
	current_lo_aoffset_ = current_hi_aoffset_ - length;
	current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - 0;
	} else {
	SetLeft();
	retval = false;
	}
	current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
	return true;
	}

	// Map an offset in A' to the corresponding offset in A
	int OffsetMap::MapBack(int aprimeoffset){
	MaybeFlushAll();
	if (aprimeoffset < 0) {return 0;}
	if (max_aprimeoffset_ <= aprimeoffset) {
	return (aprimeoffset - max_aprimeoffset_) + max_aoffset_;
	}

	// If current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_,
	// use current mapping, else move window left/right
	bool ok = true;
	while (ok && (aprimeoffset < current_lo_aprimeoffset_)) {
	ok = MoveLeft();
	}
	while (ok && (current_hi_aprimeoffset_ <= aprimeoffset)) {
	ok = MoveRight();
	}
	// So now current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_

	int aoffset = aprimeoffset - current_diff_;
	if (aoffset >= current_hi_aoffset_) {
	// A' is in an insert region, all bytes of which backmap to A=hi_aoffset_
	aoffset = current_hi_aoffset_;
	}
	return aoffset;
	}

	// Map an offset in A to the corresponding offset in A'
	int OffsetMap::MapForward(int aoffset){
	MaybeFlushAll();
	if (aoffset < 0) {return 0;}
	if (max_aoffset_ <= aoffset) {
	return (aoffset - max_aoffset_) + max_aprimeoffset_;
	}

	// If current_lo_aoffset_ <= aoffset < current_hi_aoffset_,
	// use current mapping, else move window left/right
	bool ok = true;
	while (ok && (aoffset < current_lo_aoffset_)) {
	ok = MoveLeft();
	}
	while (ok && (current_hi_aoffset_ <= aoffset)) {
	ok = MoveRight();
	}

	int aprimeoffset = aoffset + current_diff_;
	if (aprimeoffset >= current_hi_aprimeoffset_) {
	// A is in a delete region, all bytes of which map to A'=hi_aprimeoffset_
	aprimeoffset = current_hi_aprimeoffset_;
	}
	return aprimeoffset;
	}


	// static
	bool OffsetMap::CopyInserts(OffsetMap* source, OffsetMap* dest) {
	bool ok = true;
	while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
	ok = source->MoveRight();
	if (source->current_lo_aoffset_ != source->current_hi_aoffset_) {
	return false;
	}
	dest->Insert(
	source->current_hi_aprimeoffset_ - source->current_lo_aprimeoffset_);
	}
	return true;
	}

	// static
	bool OffsetMap::CopyDeletes(OffsetMap* source, OffsetMap* dest) {
	bool ok = true;
	while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
	ok = source->MoveRight();
	if (source->current_lo_aprimeoffset_ != source->current_hi_aprimeoffset_) {
	return false;
	}
	dest->Delete(source->current_hi_aoffset_ - source->current_lo_aoffset_);
	}
	return true;
	}

	// static
	void OffsetMap::ComposeOffsetMap(
	OffsetMap* g, OffsetMap* f, OffsetMap* h) {
	h->Clear();
	f->Reset();
	g->Reset();

	int lo = 0;
	for (;;) {
	// Consume delete operations in f. This moves A without moving
	// A' and A''.
	if (lo >= g->current_hi_aoffset_ && CopyInserts(g, h)) {
	if (lo >= f->current_hi_aprimeoffset_ && CopyDeletes(f, h)) {
	// fprintf(stderr,
	// "ComposeOffsetMap ERROR, f is longer than g.<br>\n");
	}

	// FlushAll(), called by Reset(), MapForward() or MapBack(), has
	// added an extra COPY_OP to f and g, so this function has
	// composed an extra COPY_OP in h from those. To avoid
	// FlushAll() adds one more extra COPY_OP to h later, dispatch
	// Flush() right now.
	h->Flush();
	return;
	}

	// Consume insert operations in g. This moves A'' without moving A
	// and A'.
	if (lo >= f->current_hi_aprimeoffset_) {
	if (!CopyDeletes(f, h)) {
	// fprintf(stderr,
	// "ComposeOffsetMap ERROR, g is longer than f.<br>\n");
	}
	}

	// Compose one operation which moves A' from lo to hi.
	int hi = min(f->current_hi_aprimeoffset_, g->current_hi_aoffset_);
	if (f->current_lo_aoffset_ != f->current_hi_aoffset_ &&
	g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
	h->Copy(hi - lo);
	} else if (f->current_lo_aoffset_ != f->current_hi_aoffset_) {
	h->Delete(hi - lo);
	} else if (g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
	h->Insert(hi - lo);
	}

	lo = hi;
	}
	}

	// For testing only -- force a mapping
	void OffsetMap::StuffIt(const string& diffs,
	int max_aoffset, int max_aprimeoffset) {
	Clear();
	diffs_ = diffs;
	max_aoffset_ = max_aoffset;
	max_aprimeoffset_ = max_aprimeoffset;
	}


	} // namespace CLD2