aboutsummaryrefslogtreecommitdiff
path: root/nxcomp/IntCache.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'nxcomp/IntCache.cpp')
-rw-r--r--nxcomp/IntCache.cpp218
1 files changed, 218 insertions, 0 deletions
diff --git a/nxcomp/IntCache.cpp b/nxcomp/IntCache.cpp
new file mode 100644
index 000000000..8262d5605
--- /dev/null
+++ b/nxcomp/IntCache.cpp
@@ -0,0 +1,218 @@
+/**************************************************************************/
+/* */
+/* Copyright (c) 2001, 2010 NoMachine, http://www.nomachine.com/. */
+/* */
+/* NXCOMP, NX protocol compression and NX extensions to this software */
+/* are copyright of NoMachine. Redistribution and use of the present */
+/* software is allowed according to terms specified in the file LICENSE */
+/* which comes in the source distribution. */
+/* */
+/* Check http://www.nomachine.com/licensing.html for applicability. */
+/* */
+/* NX and NoMachine are trademarks of Medialogic S.p.A. */
+/* */
+/* All rights reserved. */
+/* */
+/**************************************************************************/
+
+#include <string.h>
+
+#include "Misc.h"
+#include "IntCache.h"
+
+#define PANIC
+#define WARNING
+#undef TEST
+#undef DEBUG
+#undef DUMP
+
+IntCache::IntCache(unsigned int size)
+
+ : size_(size), length_(0), buffer_(new unsigned int[size]),
+ lastDiff_(0), lastValueInserted_(0), predictedBlockSize_(0)
+{
+}
+
+int IntCache::lookup(unsigned int &value, unsigned int &index,
+ unsigned int mask, unsigned int &sameDiff)
+{
+ for (unsigned int i = 0; i < length_; i++)
+ {
+ if (value == buffer_[i])
+ {
+ index = i;
+ if (i)
+ {
+ unsigned int target = (i >> 1);
+ do
+ {
+ buffer_[i] = buffer_[i - 1];
+ i--;
+ }
+ while (i > target);
+ buffer_[target] = value;
+ }
+ return 1;
+ }
+ }
+ unsigned int insertionPoint;
+ if (2 >= length_)
+ insertionPoint = length_;
+ else
+ insertionPoint = 2;
+ unsigned int start;
+ if (length_ >= size_)
+ start = size_ - 1;
+ else
+ {
+ start = length_;
+ length_++;
+ }
+ for (unsigned int k = start; k > insertionPoint; k--)
+ buffer_[k] = buffer_[k - 1];
+ buffer_[insertionPoint] = value;
+ unsigned int diff = value - lastValueInserted_;
+
+ lastValueInserted_ = (value & mask);
+ value = (diff & mask);
+ sameDiff = (value == lastDiff_);
+ if (!sameDiff)
+ {
+ lastDiff_ = value;
+
+ unsigned int lastChangeIndex = 0;
+ unsigned int lastBitIsOne = (lastDiff_ & 0x1);
+ unsigned int j = 1;
+ for (unsigned int nextMask = 0x2; nextMask & mask; nextMask <<= 1)
+ {
+ unsigned int nextBitIsOne = (lastDiff_ & nextMask);
+ if (nextBitIsOne)
+ {
+ if (!lastBitIsOne)
+ {
+ lastChangeIndex = j;
+ lastBitIsOne = nextBitIsOne;
+ }
+ }
+ else
+ {
+ if (lastBitIsOne)
+ {
+ lastChangeIndex = j;
+ lastBitIsOne = nextBitIsOne;
+ }
+ }
+ j++;
+ }
+ predictedBlockSize_ = lastChangeIndex + 1;
+ if (predictedBlockSize_ < 2)
+ predictedBlockSize_ = 2;
+ }
+ return 0;
+}
+
+void IntCache::insert(unsigned int &value, unsigned int mask)
+{
+ unsigned int insertionPoint;
+ if (2 >= length_)
+ insertionPoint = length_;
+ else
+ insertionPoint = 2;
+ unsigned int start;
+ if (length_ >= size_)
+ start = size_ - 1;
+ else
+ {
+ start = length_;
+ length_++;
+ }
+ for (unsigned int k = start; k > insertionPoint; k--)
+ buffer_[k] = buffer_[k - 1];
+ if (lastDiff_ != value)
+ {
+ lastDiff_ = value;
+ unsigned int lastChangeIndex = 0;
+ unsigned int lastBitIsOne = (lastDiff_ & 0x1);
+ unsigned int j = 1;
+ for (unsigned int nextMask = 0x2; nextMask & mask; nextMask <<= 1)
+ {
+ unsigned int nextBitIsOne = (lastDiff_ & nextMask);
+ if (nextBitIsOne)
+ {
+ if (!lastBitIsOne)
+ {
+ lastChangeIndex = j;
+ lastBitIsOne = nextBitIsOne;
+ }
+ }
+ else
+ {
+ if (lastBitIsOne)
+ {
+ lastChangeIndex = j;
+ lastBitIsOne = nextBitIsOne;
+ }
+ }
+ j++;
+ }
+ predictedBlockSize_ = lastChangeIndex + 1;
+ if (predictedBlockSize_ < 2)
+ predictedBlockSize_ = 2;
+ }
+ lastValueInserted_ += value;
+ lastValueInserted_ &= mask;
+ buffer_[insertionPoint] = lastValueInserted_;
+ value = lastValueInserted_;
+}
+
+void IntCache::push(unsigned int &value, unsigned int mask)
+{
+ //
+ // Using a memmove() appears to be slower.
+ //
+ // memmove((char *) &buffer_[1], (char *) &buffer_[0],
+ // sizeof(unsigned int) * (size_ - 1));
+ //
+ // if (length_ < size_)
+ // {
+ // length_++;
+ // }
+ //
+
+ unsigned int start;
+
+ if (length_ >= size_)
+ {
+ start = size_ - 1;
+ }
+ else
+ {
+ start = length_;
+
+ length_++;
+ }
+
+ for (unsigned int k = start; k > 0; k--)
+ {
+ buffer_[k] = buffer_[k - 1];
+ }
+
+ value &= mask;
+
+ buffer_[0] = value;
+}
+
+void IntCache::dump()
+{
+ #ifdef DUMP
+
+ *logofs << "IntCache: Dumping content of cache at "
+ << (void *) this << ":\n" << logofs_flush;
+
+ for (unsigned int i = 0; i < length_; i++)
+ {
+ *logofs << "IntCache: [" << i << "][" << buffer_[i] << "]\n";
+ }
+
+ #endif
+}