diff options
Diffstat (limited to 'application/basilisk/components/translation/cld2/internal/offsetmap.cc')
-rw-r--r-- | application/basilisk/components/translation/cld2/internal/offsetmap.cc | 569 |
1 files changed, 0 insertions, 569 deletions
diff --git a/application/basilisk/components/translation/cld2/internal/offsetmap.cc b/application/basilisk/components/translation/cld2/internal/offsetmap.cc deleted file mode 100644 index 84609a71f..000000000 --- a/application/basilisk/components/translation/cld2/internal/offsetmap.cc +++ /dev/null @@ -1,569 +0,0 @@ -// 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: %ld bytes\n", 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 - |