summaryrefslogtreecommitdiff
path: root/thirdparty/misc
diff options
context:
space:
mode:
authorRémi Verschelde <rverschelde@gmail.com>2017-04-28 18:29:15 +0200
committerRémi Verschelde <rverschelde@gmail.com>2017-04-28 21:19:23 +0200
commit2398eb6ed4832fd7b8eec778981cbd974b89634f (patch)
treee68c8db6c58fa993a0196f4f663a0064c4b17390 /thirdparty/misc
parent0a613ff9707634fcb93a009813bbbad040a4d6d8 (diff)
Move core thirdparty files to thirdparty/{minizip,misc}
Diffstat (limited to 'thirdparty/misc')
-rw-r--r--thirdparty/misc/aes256.cpp397
-rw-r--r--thirdparty/misc/aes256.h46
-rw-r--r--thirdparty/misc/base64.c118
-rw-r--r--thirdparty/misc/base64.h19
-rw-r--r--thirdparty/misc/fastlz.c551
-rw-r--r--thirdparty/misc/fastlz.h100
-rw-r--r--thirdparty/misc/hq2x.cpp2636
-rw-r--r--thirdparty/misc/hq2x.h19
-rw-r--r--thirdparty/misc/md5.cpp267
-rw-r--r--thirdparty/misc/md5.h61
-rw-r--r--thirdparty/misc/pcg.cpp15
-rw-r--r--thirdparty/misc/pcg.h14
-rw-r--r--thirdparty/misc/sha256.c245
-rw-r--r--thirdparty/misc/sha256.h50
-rw-r--r--thirdparty/misc/triangulator.cpp1550
-rw-r--r--thirdparty/misc/triangulator.h306
16 files changed, 6394 insertions, 0 deletions
diff --git a/thirdparty/misc/aes256.cpp b/thirdparty/misc/aes256.cpp
new file mode 100644
index 0000000000..dc271928b4
--- /dev/null
+++ b/thirdparty/misc/aes256.cpp
@@ -0,0 +1,397 @@
+/*
+* Byte-oriented AES-256 implementation.
+* All lookup tables replaced with 'on the fly' calculations.
+*
+* Copyright (c) 2007-2011 Ilya O. Levin, http://www.literatecode.com
+* Other contributors: Hal Finney
+*
+* Permission to use, copy, modify, and distribute this software for any
+* purpose with or without fee is hereby granted, provided that the above
+* copyright notice and this permission notice appear in all copies.
+*
+* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+#include "aes256.h"
+
+#define FD(x) (((x) >> 1) ^ (((x) & 1) ? 0x8d : 0))
+
+#define BACK_TO_TABLES
+
+static uint8_t rj_xtime(uint8_t);
+static void aes_subBytes(uint8_t *);
+static void aes_subBytes_inv(uint8_t *);
+static void aes_addRoundKey(uint8_t *, uint8_t *);
+static void aes_addRoundKey_cpy(uint8_t *, uint8_t *, uint8_t *);
+static void aes_shiftRows(uint8_t *);
+static void aes_shiftRows_inv(uint8_t *);
+static void aes_mixColumns(uint8_t *);
+static void aes_mixColumns_inv(uint8_t *);
+static void aes_expandEncKey(uint8_t *, uint8_t *);
+static void aes_expandDecKey(uint8_t *, uint8_t *);
+#ifndef BACK_TO_TABLES
+static uint8_t gf_alog(uint8_t);
+static uint8_t gf_log(uint8_t);
+static uint8_t gf_mulinv(uint8_t);
+static uint8_t rj_sbox(uint8_t);
+static uint8_t rj_sbox_inv(uint8_t);
+#endif
+
+#ifdef BACK_TO_TABLES
+
+static const uint8_t sbox[256] = {
+ 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
+ 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
+ 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
+ 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
+ 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
+ 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
+ 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
+ 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
+ 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
+ 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
+ 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
+ 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
+ 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
+ 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
+ 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
+ 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
+ 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
+ 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
+ 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
+ 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
+ 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
+ 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
+ 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
+ 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
+ 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
+ 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
+ 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
+ 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
+ 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
+ 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
+ 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
+ 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
+};
+static const uint8_t sboxinv[256] = {
+ 0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38,
+ 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
+ 0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87,
+ 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
+ 0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d,
+ 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
+ 0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2,
+ 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
+ 0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16,
+ 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
+ 0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda,
+ 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
+ 0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a,
+ 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
+ 0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02,
+ 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
+ 0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea,
+ 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
+ 0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85,
+ 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
+ 0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89,
+ 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
+ 0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20,
+ 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
+ 0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31,
+ 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
+ 0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d,
+ 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
+ 0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0,
+ 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
+ 0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26,
+ 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
+};
+
+#define rj_sbox(x) sbox[(x)]
+#define rj_sbox_inv(x) sboxinv[(x)]
+
+#else /* tableless subroutines */
+
+/* -------------------------------------------------------------------------- */
+static uint8_t gf_alog(uint8_t x) // calculate anti-logarithm gen 3
+{
+ uint8_t y = 1, i;
+
+ for (i = 0; i < x; i++) y ^= rj_xtime(y);
+
+ return y;
+} /* gf_alog */
+
+/* -------------------------------------------------------------------------- */
+static uint8_t gf_log(uint8_t x) // calculate logarithm gen 3
+{
+ uint8_t y, i = 0;
+
+ if (x)
+ for (i = 1, y = 1; i > 0; i++ )
+ {
+ y ^= rj_xtime(y);
+ if (y == x) break;
+ }
+
+ return i;
+} /* gf_log */
+
+
+/* -------------------------------------------------------------------------- */
+static uint8_t gf_mulinv(uint8_t x) // calculate multiplicative inverse
+{
+ return (x) ? gf_alog(255 - gf_log(x)) : 0;
+} /* gf_mulinv */
+
+/* -------------------------------------------------------------------------- */
+static uint8_t rj_sbox(uint8_t x)
+{
+ uint8_t y, sb;
+
+ sb = y = gf_mulinv(x);
+ y = (uint8_t)(y << 1) | (y >> 7), sb ^= y;
+ y = (uint8_t)(y << 1) | (y >> 7), sb ^= y;
+ y = (uint8_t)(y << 1) | (y >> 7), sb ^= y;
+ y = (uint8_t)(y << 1) | (y >> 7), sb ^= y;
+
+ return (sb ^ 0x63);
+} /* rj_sbox */
+
+/* -------------------------------------------------------------------------- */
+static uint8_t rj_sbox_inv(uint8_t x)
+{
+ uint8_t y, sb;
+
+ y = x ^ 0x63;
+ sb = y = (uint8_t)(y << 1) | (y >> 7);
+ y = (uint8_t)(y << 2) | (y >> 6);
+ sb ^= y;
+ y = (uint8_t)(y << 3) | (y >> 5);
+ sb ^= y;
+
+ return gf_mulinv(sb);
+} /* rj_sbox_inv */
+
+#endif
+
+/* -------------------------------------------------------------------------- */
+static uint8_t rj_xtime(uint8_t x)
+{
+ uint8_t y = (uint8_t)(x << 1);
+ return (x & 0x80) ? (y ^ 0x1b) : y;
+} /* rj_xtime */
+
+/* -------------------------------------------------------------------------- */
+static void aes_subBytes(uint8_t *buf)
+{
+ register uint8_t i = 16;
+
+ while (i--) buf[i] = rj_sbox(buf[i]);
+} /* aes_subBytes */
+
+/* -------------------------------------------------------------------------- */
+static void aes_subBytes_inv(uint8_t *buf)
+{
+ register uint8_t i = 16;
+
+ while (i--) buf[i] = rj_sbox_inv(buf[i]);
+} /* aes_subBytes_inv */
+
+/* -------------------------------------------------------------------------- */
+static void aes_addRoundKey(uint8_t *buf, uint8_t *key)
+{
+ register uint8_t i = 16;
+
+ while (i--) buf[i] ^= key[i];
+} /* aes_addRoundKey */
+
+/* -------------------------------------------------------------------------- */
+static void aes_addRoundKey_cpy(uint8_t *buf, uint8_t *key, uint8_t *cpk)
+{
+ register uint8_t i = 16;
+
+ while (i--) buf[i] ^= (cpk[i] = key[i]), cpk[16 + i] = key[16 + i];
+} /* aes_addRoundKey_cpy */
+
+
+/* -------------------------------------------------------------------------- */
+static void aes_shiftRows(uint8_t *buf)
+{
+ register uint8_t i, j; /* to make it potentially parallelable :) */
+
+ i = buf[1], buf[1] = buf[5], buf[5] = buf[9], buf[9] = buf[13], buf[13] = i;
+ i = buf[10], buf[10] = buf[2], buf[2] = i;
+ j = buf[3], buf[3] = buf[15], buf[15] = buf[11], buf[11] = buf[7], buf[7] = j;
+ j = buf[14], buf[14] = buf[6], buf[6] = j;
+
+} /* aes_shiftRows */
+
+/* -------------------------------------------------------------------------- */
+static void aes_shiftRows_inv(uint8_t *buf)
+{
+ register uint8_t i, j; /* same as above :) */
+
+ i = buf[1], buf[1] = buf[13], buf[13] = buf[9], buf[9] = buf[5], buf[5] = i;
+ i = buf[2], buf[2] = buf[10], buf[10] = i;
+ j = buf[3], buf[3] = buf[7], buf[7] = buf[11], buf[11] = buf[15], buf[15] = j;
+ j = buf[6], buf[6] = buf[14], buf[14] = j;
+
+} /* aes_shiftRows_inv */
+
+/* -------------------------------------------------------------------------- */
+static void aes_mixColumns(uint8_t *buf)
+{
+ register uint8_t i, a, b, c, d, e;
+
+ for (i = 0; i < 16; i += 4)
+ {
+ a = buf[i];
+ b = buf[i + 1];
+ c = buf[i + 2];
+ d = buf[i + 3];
+ e = a ^ b ^ c ^ d;
+ buf[i] ^= e ^ rj_xtime(a ^ b);
+ buf[i + 1] ^= e ^ rj_xtime(b ^ c);
+ buf[i + 2] ^= e ^ rj_xtime(c ^ d);
+ buf[i + 3] ^= e ^ rj_xtime(d ^ a);
+ }
+} /* aes_mixColumns */
+
+/* -------------------------------------------------------------------------- */
+void aes_mixColumns_inv(uint8_t *buf)
+{
+ register uint8_t i, a, b, c, d, e, x, y, z;
+
+ for (i = 0; i < 16; i += 4)
+ {
+ a = buf[i];
+ b = buf[i + 1];
+ c = buf[i + 2];
+ d = buf[i + 3];
+ e = a ^ b ^ c ^ d;
+ z = rj_xtime(e);
+ x = e ^ rj_xtime(rj_xtime(z ^ a ^ c));
+ y = e ^ rj_xtime(rj_xtime(z ^ b ^ d));
+ buf[i] ^= x ^ rj_xtime(a ^ b);
+ buf[i + 1] ^= y ^ rj_xtime(b ^ c);
+ buf[i + 2] ^= x ^ rj_xtime(c ^ d);
+ buf[i + 3] ^= y ^ rj_xtime(d ^ a);
+ }
+} /* aes_mixColumns_inv */
+
+/* -------------------------------------------------------------------------- */
+static void aes_expandEncKey(uint8_t *k, uint8_t *rc)
+{
+ register uint8_t i;
+
+ k[0] ^= rj_sbox(k[29]) ^ (*rc);
+ k[1] ^= rj_sbox(k[30]);
+ k[2] ^= rj_sbox(k[31]);
+ k[3] ^= rj_sbox(k[28]);
+ *rc = rj_xtime( *rc);
+
+ for(i = 4; i < 16; i += 4) k[i] ^= k[i - 4], k[i + 1] ^= k[i - 3],
+ k[i + 2] ^= k[i - 2], k[i + 3] ^= k[i - 1];
+ k[16] ^= rj_sbox(k[12]);
+ k[17] ^= rj_sbox(k[13]);
+ k[18] ^= rj_sbox(k[14]);
+ k[19] ^= rj_sbox(k[15]);
+
+ for(i = 20; i < 32; i += 4) k[i] ^= k[i - 4], k[i + 1] ^= k[i - 3],
+ k[i + 2] ^= k[i - 2], k[i + 3] ^= k[i - 1];
+
+} /* aes_expandEncKey */
+
+/* -------------------------------------------------------------------------- */
+void aes_expandDecKey(uint8_t *k, uint8_t *rc)
+{
+ uint8_t i;
+
+ for(i = 28; i > 16; i -= 4) k[i + 0] ^= k[i - 4], k[i + 1] ^= k[i - 3],
+ k[i + 2] ^= k[i - 2], k[i + 3] ^= k[i - 1];
+
+ k[16] ^= rj_sbox(k[12]);
+ k[17] ^= rj_sbox(k[13]);
+ k[18] ^= rj_sbox(k[14]);
+ k[19] ^= rj_sbox(k[15]);
+
+ for(i = 12; i > 0; i -= 4) k[i + 0] ^= k[i - 4], k[i + 1] ^= k[i - 3],
+ k[i + 2] ^= k[i - 2], k[i + 3] ^= k[i - 1];
+
+ *rc = FD(*rc);
+ k[0] ^= rj_sbox(k[29]) ^ (*rc);
+ k[1] ^= rj_sbox(k[30]);
+ k[2] ^= rj_sbox(k[31]);
+ k[3] ^= rj_sbox(k[28]);
+} /* aes_expandDecKey */
+
+
+/* -------------------------------------------------------------------------- */
+void aes256_init(aes256_context *ctx, uint8_t *k)
+{
+ uint8_t rcon = 1;
+ register uint8_t i;
+
+ for (i = 0; i < sizeof(ctx->key); i++) ctx->enckey[i] = ctx->deckey[i] = k[i];
+ for (i = 8; --i;) aes_expandEncKey(ctx->deckey, &rcon);
+} /* aes256_init */
+
+/* -------------------------------------------------------------------------- */
+void aes256_done(aes256_context *ctx)
+{
+ register uint8_t i;
+
+ for (i = 0; i < sizeof(ctx->key); i++)
+ ctx->key[i] = ctx->enckey[i] = ctx->deckey[i] = 0;
+} /* aes256_done */
+
+/* -------------------------------------------------------------------------- */
+void aes256_encrypt_ecb(aes256_context *ctx, uint8_t *buf)
+{
+ uint8_t i, rcon;
+
+ aes_addRoundKey_cpy(buf, ctx->enckey, ctx->key);
+ for(i = 1, rcon = 1; i < 14; ++i)
+ {
+ aes_subBytes(buf);
+ aes_shiftRows(buf);
+ aes_mixColumns(buf);
+ if( i & 1 ) aes_addRoundKey( buf, &ctx->key[16]);
+ else aes_expandEncKey(ctx->key, &rcon), aes_addRoundKey(buf, ctx->key);
+ }
+ aes_subBytes(buf);
+ aes_shiftRows(buf);
+ aes_expandEncKey(ctx->key, &rcon);
+ aes_addRoundKey(buf, ctx->key);
+} /* aes256_encrypt */
+
+/* -------------------------------------------------------------------------- */
+void aes256_decrypt_ecb(aes256_context *ctx, uint8_t *buf)
+{
+ uint8_t i, rcon;
+
+ aes_addRoundKey_cpy(buf, ctx->deckey, ctx->key);
+ aes_shiftRows_inv(buf);
+ aes_subBytes_inv(buf);
+
+ for (i = 14, rcon = 0x80; --i;)
+ {
+ if( ( i & 1 ) )
+ {
+ aes_expandDecKey(ctx->key, &rcon);
+ aes_addRoundKey(buf, &ctx->key[16]);
+ }
+ else aes_addRoundKey(buf, ctx->key);
+ aes_mixColumns_inv(buf);
+ aes_shiftRows_inv(buf);
+ aes_subBytes_inv(buf);
+ }
+ aes_addRoundKey( buf, ctx->key);
+} /* aes256_decrypt */
diff --git a/thirdparty/misc/aes256.h b/thirdparty/misc/aes256.h
new file mode 100644
index 0000000000..8fcc25a4de
--- /dev/null
+++ b/thirdparty/misc/aes256.h
@@ -0,0 +1,46 @@
+/*
+* Byte-oriented AES-256 implementation.
+* All lookup tables replaced with 'on the fly' calculations.
+*
+* Copyright (c) 2007-2009 Ilya O. Levin, http://www.literatecode.com
+* Other contributors: Hal Finney
+*
+* Permission to use, copy, modify, and distribute this software for any
+* purpose with or without fee is hereby granted, provided that the above
+* copyright notice and this permission notice appear in all copies.
+*
+* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef AES_256_H
+#define AES_256_H
+
+#include "typedefs.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+ typedef struct {
+ uint8_t key[32];
+ uint8_t enckey[32];
+ uint8_t deckey[32];
+ } aes256_context;
+
+
+ void aes256_init(aes256_context *, uint8_t * /* key */);
+ void aes256_done(aes256_context *);
+ void aes256_encrypt_ecb(aes256_context *, uint8_t * /* plaintext */);
+ void aes256_decrypt_ecb(aes256_context *, uint8_t * /* cipertext */);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/thirdparty/misc/base64.c b/thirdparty/misc/base64.c
new file mode 100644
index 0000000000..0929ae5db5
--- /dev/null
+++ b/thirdparty/misc/base64.c
@@ -0,0 +1,118 @@
+/*
+ * File: base64.c
+ * Description: Simple BASE64 conversion methods
+ * Author: Ari Edelkind
+ * License: Public Domain
+ * Website: http://episec.com/people/edelkind/c.html
+ */
+
+#include <string.h>
+
+char b64string[] =
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+
+long base64_encode (to, from, len)
+ char *to, *from;
+ unsigned int len;
+{
+ char *fromp = from;
+ char *top = to;
+ unsigned char cbyte;
+ unsigned char obyte;
+ char end[3];
+
+ for (; len >= 3; len -= 3) {
+ cbyte = *fromp++;
+ *top++ = b64string[(int)(cbyte >> 2)];
+ obyte = (cbyte << 4) & 0x30; /* 0011 0000 */
+
+ cbyte = *fromp++;
+ obyte |= (cbyte >> 4); /* 0000 1111 */
+ *top++ = b64string[(int)obyte];
+ obyte = (cbyte << 2) & 0x3C; /* 0011 1100 */
+
+ cbyte = *fromp++;
+ obyte |= (cbyte >> 6); /* 0000 0011 */
+ *top++ = b64string[(int)obyte];
+ *top++ = b64string[(int)(cbyte & 0x3F)];/* 0011 1111 */
+ }
+
+ if (len) {
+ end[0] = *fromp++;
+ if (--len) end[1] = *fromp++; else end[1] = 0;
+ end[2] = 0;
+
+ cbyte = end[0];
+ *top++ = b64string[(int)(cbyte >> 2)];
+ obyte = (cbyte << 4) & 0x30; /* 0011 0000 */
+
+ cbyte = end[1];
+ obyte |= (cbyte >> 4);
+ *top++ = b64string[(int)obyte];
+ obyte = (cbyte << 2) & 0x3C; /* 0011 1100 */
+
+ if (len) *top++ = b64string[(int)obyte];
+ else *top++ = '=';
+ *top++ = '=';
+ }
+ *top = 0;
+ return top - to;
+}
+
+/* badchar(): check if c is decent; puts either the */
+/* location of c or null into p. */
+#define badchar(c,p) (!(p = memchr(b64string, c, 64)))
+
+long base64_decode (to, from, len)
+ char *to, *from;
+ unsigned int len;
+{
+ char *fromp = from;
+ char *top = to;
+ char *p;
+ unsigned char cbyte;
+ unsigned char obyte;
+ int padding = 0;
+
+ for (; len >= 4; len -= 4) {
+ if ((cbyte = *fromp++) == '=') cbyte = 0;
+ else {
+ if (badchar(cbyte, p)) return -1;
+ cbyte = (p - b64string);
+ }
+ obyte = cbyte << 2; /* 1111 1100 */
+
+ if ((cbyte = *fromp++) == '=') cbyte = 0;
+ else {
+ if (badchar(cbyte, p)) return -1;
+ cbyte = p - b64string;
+ }
+ obyte |= cbyte >> 4; /* 0000 0011 */
+ *top++ = obyte;
+
+ obyte = cbyte << 4; /* 1111 0000 */
+ if ((cbyte = *fromp++) == '=') { cbyte = 0; padding++; }
+ else {
+ padding = 0;
+ if (badchar (cbyte, p)) return -1;
+ cbyte = p - b64string;
+ }
+ obyte |= cbyte >> 2; /* 0000 1111 */
+ *top++ = obyte;
+
+ obyte = cbyte << 6; /* 1100 0000 */
+ if ((cbyte = *fromp++) == '=') { cbyte = 0; padding++; }
+ else {
+ padding = 0;
+ if (badchar (cbyte, p)) return -1;
+ cbyte = p - b64string;
+ }
+ obyte |= cbyte; /* 0011 1111 */
+ *top++ = obyte;
+ }
+
+ *top = 0;
+ if (len) return -1;
+ return (top - to) - padding;
+}
+
diff --git a/thirdparty/misc/base64.h b/thirdparty/misc/base64.h
new file mode 100644
index 0000000000..456ef1811b
--- /dev/null
+++ b/thirdparty/misc/base64.h
@@ -0,0 +1,19 @@
+/*
+ * File: base64.h
+ * Description: Simple BASE64 conversion methods
+ * Author: Ari Edelkind
+ * License: Public Domain
+ * Website: http://episec.com/people/edelkind/c.html
+ */
+
+#ifndef BASE64_H
+#define BASE64_H
+
+extern "C" {
+
+uint32_t base64_encode (char* to, char* from, uint32_t len);
+uint32_t base64_decode (char* to, char* from, uint32_t len);
+
+};
+
+#endif /* BASE64_H */
diff --git a/thirdparty/misc/fastlz.c b/thirdparty/misc/fastlz.c
new file mode 100644
index 0000000000..508f6ea2ae
--- /dev/null
+++ b/thirdparty/misc/fastlz.c
@@ -0,0 +1,551 @@
+ /*
+ FastLZ - lightning-fast lossless compression library
+
+ Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+ Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+ Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+*/
+
+#if !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
+
+/*
+ * Always check for bound when decompressing.
+ * Generally it is best to leave it defined.
+ */
+#define FASTLZ_SAFE
+
+/*
+ * Give hints to the compiler for branch prediction optimization.
+ */
+#if defined(__GNUC__) && (__GNUC__ > 2)
+#define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
+#define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
+#else
+#define FASTLZ_EXPECT_CONDITIONAL(c) (c)
+#define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
+#endif
+
+/*
+ * Use inlined functions for supported systems.
+ */
+#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
+#define FASTLZ_INLINE inline
+#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
+#define FASTLZ_INLINE __inline
+#else
+#define FASTLZ_INLINE
+#endif
+
+/*
+ * Prevent accessing more than 8-bit at once, except on x86 architectures.
+ */
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_STRICT_ALIGN
+#if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_M_IX86) /* Intel, MSVC */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__386)
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_X86_) /* MinGW */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__I86__) /* Digital Mars */
+#undef FASTLZ_STRICT_ALIGN
+#endif
+#endif
+
+/*
+ * FIXME: use preprocessor magic to set this on different platforms!
+ */
+typedef unsigned char flzuint8;
+typedef unsigned short flzuint16;
+typedef unsigned int flzuint32;
+
+/* prototypes */
+int fastlz_compress(const void* input, int length, void* output);
+int fastlz_compress_level(int level, const void* input, int length, void* output);
+int fastlz_decompress(const void* input, int length, void* output, int maxout);
+
+#define MAX_COPY 32
+#define MAX_LEN 264 /* 256 + 8 */
+#define MAX_DISTANCE 8192
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_READU16(p) *((const flzuint16*)(p))
+#else
+#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
+#endif
+
+#define HASH_LOG 13
+#define HASH_SIZE (1<< HASH_LOG)
+#define HASH_MASK (HASH_SIZE-1)
+#define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 1
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz1_compress
+#define FASTLZ_DECOMPRESSOR fastlz1_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
+#include "fastlz.c"
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 2
+
+#undef MAX_DISTANCE
+#define MAX_DISTANCE 8191
+#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz2_compress
+#define FASTLZ_DECOMPRESSOR fastlz2_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
+#include "fastlz.c"
+
+int fastlz_compress(const void* input, int length, void* output)
+{
+ /* for short block, choose fastlz1 */
+ if(length < 65536)
+ return fastlz1_compress(input, length, output);
+
+ /* else... */
+ return fastlz2_compress(input, length, output);
+}
+
+int fastlz_decompress(const void* input, int length, void* output, int maxout)
+{
+ /* magic identifier for compression level */
+ int level = ((*(const flzuint8*)input) >> 5) + 1;
+
+ if(level == 1)
+ return fastlz1_decompress(input, length, output, maxout);
+ if(level == 2)
+ return fastlz2_decompress(input, length, output, maxout);
+
+ /* unknown level, trigger error */
+ return 0;
+}
+
+int fastlz_compress_level(int level, const void* input, int length, void* output)
+{
+ if(level == 1)
+ return fastlz1_compress(input, length, output);
+ if(level == 2)
+ return fastlz2_compress(input, length, output);
+
+ return 0;
+}
+
+#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
+
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
+{
+ const flzuint8* ip = (const flzuint8*) input;
+ const flzuint8* ip_bound = ip + length - 2;
+ const flzuint8* ip_limit = ip + length - 12;
+ flzuint8* op = (flzuint8*) output;
+
+ const flzuint8* htab[HASH_SIZE];
+ const flzuint8** hslot;
+ flzuint32 hval;
+
+ flzuint32 copy;
+
+ /* sanity check */
+ if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
+ {
+ if(length)
+ {
+ /* create literal copy only */
+ *op++ = length-1;
+ ip_bound++;
+ while(ip <= ip_bound)
+ *op++ = *ip++;
+ return length+1;
+ }
+ else
+ return 0;
+ }
+
+ /* initializes hash table */
+ for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
+ *hslot = ip;
+
+ /* we start with literal copy */
+ copy = 2;
+ *op++ = MAX_COPY-1;
+ *op++ = *ip++;
+ *op++ = *ip++;
+
+ /* main loop */
+ while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
+ {
+ const flzuint8* ref;
+ flzuint32 distance;
+
+ /* minimum match length */
+ flzuint32 len = 3;
+
+ /* comparison starting-point */
+ const flzuint8* anchor = ip;
+
+ /* check for a run */
+#if FASTLZ_LEVEL==2
+ if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
+ {
+ distance = 1;
+ ip += 3;
+ ref = anchor - 1 + 3;
+ goto match;
+ }
+#endif
+
+ /* find potential match */
+ HASH_FUNCTION(hval,ip);
+ hslot = htab + hval;
+ ref = htab[hval];
+
+ /* calculate distance to the match */
+ distance = anchor - ref;
+
+ /* update hash table */
+ *hslot = anchor;
+
+ /* is this a match? check the first 3 bytes */
+ if(distance==0 ||
+#if FASTLZ_LEVEL==1
+ (distance >= MAX_DISTANCE) ||
+#else
+ (distance >= MAX_FARDISTANCE) ||
+#endif
+ *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
+ goto literal;
+
+#if FASTLZ_LEVEL==2
+ /* far, needs at least 5-byte match */
+ if(distance >= MAX_DISTANCE)
+ {
+ if(*ip++ != *ref++ || *ip++!= *ref++)
+ goto literal;
+ len += 2;
+ }
+
+ match:
+#endif
+
+ /* last matched byte */
+ ip = anchor + len;
+
+ /* distance is biased */
+ distance--;
+
+ if(!distance)
+ {
+ /* zero distance means a run */
+ flzuint8 x = ip[-1];
+ while(ip < ip_bound)
+ if(*ref++ != x) break; else ip++;
+ }
+ else
+ for(;;)
+ {
+ /* safe because the outer check against ip limit */
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ if(*ref++ != *ip++) break;
+ while(ip < ip_bound)
+ if(*ref++ != *ip++) break;
+ break;
+ }
+
+ /* if we have copied something, adjust the copy count */
+ if(copy)
+ /* copy is biased, '0' means 1 byte copy */
+ *(op-copy-1) = copy-1;
+ else
+ /* back, to overwrite the copy count */
+ op--;
+
+ /* reset literal counter */
+ copy = 0;
+
+ /* length is biased, '1' means a match of 3 bytes */
+ ip -= 3;
+ len = ip - anchor;
+
+ /* encode the match */
+#if FASTLZ_LEVEL==2
+ if(distance < MAX_DISTANCE)
+ {
+ if(len < 7)
+ {
+ *op++ = (len << 5) + (distance >> 8);
+ *op++ = (distance & 255);
+ }
+ else
+ {
+ *op++ = (7 << 5) + (distance >> 8);
+ for(len-=7; len >= 255; len-= 255)
+ *op++ = 255;
+ *op++ = len;
+ *op++ = (distance & 255);
+ }
+ }
+ else
+ {
+ /* far away, but not yet in the another galaxy... */
+ if(len < 7)
+ {
+ distance -= MAX_DISTANCE;
+ *op++ = (len << 5) + 31;
+ *op++ = 255;
+ *op++ = distance >> 8;
+ *op++ = distance & 255;
+ }
+ else
+ {
+ distance -= MAX_DISTANCE;
+ *op++ = (7 << 5) + 31;
+ for(len-=7; len >= 255; len-= 255)
+ *op++ = 255;
+ *op++ = len;
+ *op++ = 255;
+ *op++ = distance >> 8;
+ *op++ = distance & 255;
+ }
+ }
+#else
+
+ if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
+ while(len > MAX_LEN-2)
+ {
+ *op++ = (7 << 5) + (distance >> 8);
+ *op++ = MAX_LEN - 2 - 7 -2;
+ *op++ = (distance & 255);
+ len -= MAX_LEN-2;
+ }
+
+ if(len < 7)
+ {
+ *op++ = (len << 5) + (distance >> 8);
+ *op++ = (distance & 255);
+ }
+ else
+ {
+ *op++ = (7 << 5) + (distance >> 8);
+ *op++ = len - 7;
+ *op++ = (distance & 255);
+ }
+#endif
+
+ /* update the hash at match boundary */
+ HASH_FUNCTION(hval,ip);
+ htab[hval] = ip++;
+ HASH_FUNCTION(hval,ip);
+ htab[hval] = ip++;
+
+ /* assuming literal copy */
+ *op++ = MAX_COPY-1;
+
+ continue;
+
+ literal:
+ *op++ = *anchor++;
+ ip = anchor;
+ copy++;
+ if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
+ {
+ copy = 0;
+ *op++ = MAX_COPY-1;
+ }
+ }
+
+ /* left-over as literal copy */
+ ip_bound++;
+ while(ip <= ip_bound)
+ {
+ *op++ = *ip++;
+ copy++;
+ if(copy == MAX_COPY)
+ {
+ copy = 0;
+ *op++ = MAX_COPY-1;
+ }
+ }
+
+ /* if we have copied something, adjust the copy length */
+ if(copy)
+ *(op-copy-1) = copy-1;
+ else
+ op--;
+
+#if FASTLZ_LEVEL==2
+ /* marker for fastlz2 */
+ *(flzuint8*)output |= (1 << 5);
+#endif
+
+ return op - (flzuint8*)output;
+}
+
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
+{
+ const flzuint8* ip = (const flzuint8*) input;
+ const flzuint8* ip_limit = ip + length;
+ flzuint8* op = (flzuint8*) output;
+ flzuint8* op_limit = op + maxout;
+ flzuint32 ctrl = (*ip++) & 31;
+ int loop = 1;
+
+ do
+ {
+ const flzuint8* ref = op;
+ flzuint32 len = ctrl >> 5;
+ flzuint32 ofs = (ctrl & 31) << 8;
+
+ if(ctrl >= 32)
+ {
+#if FASTLZ_LEVEL==2
+ flzuint8 code;
+#endif
+ len--;
+ ref -= ofs;
+ if (len == 7-1)
+#if FASTLZ_LEVEL==1
+ len += *ip++;
+ ref -= *ip++;
+#else
+ do
+ {
+ code = *ip++;
+ len += code;
+ } while (code==255);
+ code = *ip++;
+ ref -= code;
+
+ /* match from 16-bit distance */
+ if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
+ if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
+ {
+ ofs = (*ip++) << 8;
+ ofs += *ip++;
+ ref = op - ofs - MAX_DISTANCE;
+ }
+#endif
+
+#ifdef FASTLZ_SAFE
+ if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
+ return 0;
+
+ if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
+ return 0;
+#endif
+
+ if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
+ ctrl = *ip++;
+ else
+ loop = 0;
+
+ if(ref == op)
+ {
+ /* optimize copy for a run */
+ flzuint8 b = ref[-1];
+ *op++ = b;
+ *op++ = b;
+ *op++ = b;
+ for(; len; --len)
+ *op++ = b;
+ }
+ else
+ {
+#if !defined(FASTLZ_STRICT_ALIGN)
+ const flzuint16* p;
+ flzuint16* q;
+#endif
+ /* copy from reference */
+ ref--;
+ *op++ = *ref++;
+ *op++ = *ref++;
+ *op++ = *ref++;
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+ /* copy a byte, so that now it's word aligned */
+ if(len & 1)
+ {
+ *op++ = *ref++;
+ len--;
+ }
+
+ /* copy 16-bit at once */
+ q = (flzuint16*) op;
+ op += len;
+ p = (const flzuint16*) ref;
+ for(len>>=1; len > 4; len-=4)
+ {
+ *q++ = *p++;
+ *q++ = *p++;
+ *q++ = *p++;
+ *q++ = *p++;
+ }
+ for(; len; --len)
+ *q++ = *p++;
+#else
+ for(; len; --len)
+ *op++ = *ref++;
+#endif
+ }
+ }
+ else
+ {
+ ctrl++;
+#ifdef FASTLZ_SAFE
+ if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
+ return 0;
+ if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
+ return 0;
+#endif
+
+ *op++ = *ip++;
+ for(--ctrl; ctrl; ctrl--)
+ *op++ = *ip++;
+
+ loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
+ if(loop)
+ ctrl = *ip++;
+ }
+ }
+ while(FASTLZ_EXPECT_CONDITIONAL(loop));
+
+ return op - (flzuint8*)output;
+}
+
+#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
diff --git a/thirdparty/misc/fastlz.h b/thirdparty/misc/fastlz.h
new file mode 100644
index 0000000000..e5ca8dfc02
--- /dev/null
+++ b/thirdparty/misc/fastlz.h
@@ -0,0 +1,100 @@
+/*
+ FastLZ - lightning-fast lossless compression library
+
+ Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+ Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+ Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+*/
+
+#ifndef FASTLZ_H
+#define FASTLZ_H
+
+#define FASTLZ_VERSION 0x000100
+
+#define FASTLZ_VERSION_MAJOR 0
+#define FASTLZ_VERSION_MINOR 0
+#define FASTLZ_VERSION_REVISION 0
+
+#define FASTLZ_VERSION_STRING "0.1.0"
+
+#if defined (__cplusplus)
+extern "C" {
+#endif
+
+/**
+ Compress a block of data in the input buffer and returns the size of
+ compressed block. The size of input buffer is specified by length. The
+ minimum input buffer size is 16.
+
+ The output buffer must be at least 5% larger than the input buffer
+ and can not be smaller than 66 bytes.
+
+ If the input is not compressible, the return value might be larger than
+ length (input buffer size).
+
+ The input buffer and the output buffer can not overlap.
+*/
+
+int fastlz_compress(const void* input, int length, void* output);
+
+/**
+ Decompress a block of compressed data and returns the size of the
+ decompressed block. If error occurs, e.g. the compressed data is
+ corrupted or the output buffer is not large enough, then 0 (zero)
+ will be returned instead.
+
+ The input buffer and the output buffer can not overlap.
+
+ Decompression is memory safe and guaranteed not to write the output buffer
+ more than what is specified in maxout.
+ */
+
+int fastlz_decompress(const void* input, int length, void* output, int maxout);
+
+/**
+ Compress a block of data in the input buffer and returns the size of
+ compressed block. The size of input buffer is specified by length. The
+ minimum input buffer size is 16.
+
+ The output buffer must be at least 5% larger than the input buffer
+ and can not be smaller than 66 bytes.
+
+ If the input is not compressible, the return value might be larger than
+ length (input buffer size).
+
+ The input buffer and the output buffer can not overlap.
+
+ Compression level can be specified in parameter level. At the moment,
+ only level 1 and level 2 are supported.
+ Level 1 is the fastest compression and generally useful for short data.
+ Level 2 is slightly slower but it gives better compression ratio.
+
+ Note that the compressed data, regardless of the level, can always be
+ decompressed using the function fastlz_decompress above.
+*/
+
+int fastlz_compress_level(int level, const void* input, int length, void* output);
+
+#if defined (__cplusplus)
+}
+#endif
+
+#endif /* FASTLZ_H */
diff --git a/thirdparty/misc/hq2x.cpp b/thirdparty/misc/hq2x.cpp
new file mode 100644
index 0000000000..7ebb505d64
--- /dev/null
+++ b/thirdparty/misc/hq2x.cpp
@@ -0,0 +1,2636 @@
+/*
+ * Copyright 2016 Bruno Ribeiro
+ *
+ * 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.
+ */
+
+
+#include "hq2x.h"
+#include "math_funcs.h"
+
+
+static const uint32_t AMASK = 0xFF000000;
+static const uint32_t YMASK = 0x00FF0000;
+static const uint32_t UMASK = 0x0000FF00;
+static const uint32_t VMASK = 0x000000FF;
+
+_FORCE_INLINE_ static uint32_t ARGBtoAYUV(
+ uint32_t value )
+{
+ uint32_t A, R, G, B, Y, U, V;
+//todo big endian check
+ A = value >> 24;
+ R = (value >> 16) & 0xFF;
+ G = (value >> 8) & 0xFF;
+ B = value & 0xFF;
+
+ Y = Math::fast_ftoi( 0.299 * R + 0.587 * G + 0.114 * B);
+ U = Math::fast_ftoi(-0.169 * R - 0.331 * G + 0.5 * B) + 128;
+ V = Math::fast_ftoi( 0.5 * R - 0.419 * G - 0.081 * B) + 128;
+ return (A << 24) + (Y << 16) + (U << 8) + V;
+}
+
+
+/*
+ * Use this function for sharper images (good for cartoon style, used by DOSBOX)
+ */
+
+_FORCE_INLINE_ static bool isDifferent(
+ uint32_t color1,
+ uint32_t color2,
+ uint32_t trY,
+ uint32_t trU,
+ uint32_t trV,
+ uint32_t trA )
+{
+ color1 = ARGBtoAYUV(color1);
+ color2 = ARGBtoAYUV(color2);
+
+ uint32_t value;
+
+ value = ((color1 & YMASK) - (color2 & YMASK));
+ value = (value ^ (value >> 31)) - (value >> 31);
+ if (value > trY) return true;
+
+ value = ((color1 & UMASK) - (color2 & UMASK));
+ value = (value ^ (value >> 31)) - (value >> 31);
+ if (value > trU) return true;
+
+ value = ((color1 & VMASK) - (color2 & VMASK));
+ value = (value ^ (value >> 31)) - (value >> 31);
+ if (value > trV) return true;
+
+ value = ((color1 & AMASK) - (color2 & AMASK));
+ value = (value ^ (value >> 31)) - (value >> 31);
+ if (value > trA) return true;
+
+ return false;
+
+}
+
+
+
+#define MASK_RB 0x00FF00FF
+#define MASK_G 0x0000FF00
+#define MASK_A 0xFF000000
+
+
+/**
+ * @brief Mixes two colors using the given weights.
+ */
+#define HQX_MIX_2(C0,C1,W0,W1) \
+ ((((C0 & MASK_RB) * W0 + (C1 & MASK_RB) * W1) / (W0 + W1)) & MASK_RB) | \
+ ((((C0 & MASK_G) * W0 + (C1 & MASK_G) * W1) / (W0 + W1)) & MASK_G) | \
+ ((((((C0 & MASK_A) >> 8) * W0 + ((C1 & MASK_A) >> 8) * W1) / (W0 + W1)) << 8) & MASK_A)
+
+/**
+ * @brief Mixes three colors using the given weights.
+ */
+#define HQX_MIX_3(C0,C1,C2,W0,W1,W2) \
+ ((((C0 & MASK_RB) * W0 + (C1 & MASK_RB) * W1 + (C2 & MASK_RB) * W2) / (W0 + W1 + W2)) & MASK_RB) | \
+ ((((C0 & MASK_G) * W0 + (C1 & MASK_G) * W1 + (C2 & MASK_G) * W2) / (W0 + W1 + W2)) & MASK_G) | \
+ ((((((C0 & MASK_A) >> 8) * W0 + ((C1 & MASK_A) >> 8) * W1 + ((C2 & MASK_A) >> 8) * W2) / (W0 + W1 + W2)) << 8) & MASK_A)
+
+
+#define MIX_00_4 *output = w[4];
+#define MIX_00_MIX_00_4_0_3_1 *output = HQX_MIX_2(w[4],w[0],3U,1U);
+#define MIX_00_4_3_3_1 *output = HQX_MIX_2(w[4],w[3],3U,1U);
+#define MIX_00_4_1_3_1 *output = HQX_MIX_2(w[4],w[1],3U,1U);
+#define MIX_00_3_1_1_1 *output = HQX_MIX_2(w[3],w[1],1U,1U);
+#define MIX_00_4_3_1_2_1_1 *output = HQX_MIX_3(w[4],w[3],w[1],2U,1U,1U);
+#define MIX_00_4_3_1_2_7_7 *output = HQX_MIX_3(w[4],w[3],w[1],2U,7U,7U);
+#define MIX_00_4_0_1_2_1_1 *output = HQX_MIX_3(w[4],w[0],w[1],2U,1U,1U);
+#define MIX_00_4_0_3_2_1_1 *output = HQX_MIX_3(w[4],w[0],w[3],2U,1U,1U);
+#define MIX_00_4_1_3_5_2_1 *output = HQX_MIX_3(w[4],w[1],w[3],5U,2U,1U);
+#define MIX_00_4_3_1_5_2_1 *output = HQX_MIX_3(w[4],w[3],w[1],5U,2U,1U);
+#define MIX_00_4_3_1_6_1_1 *output = HQX_MIX_3(w[4],w[3],w[1],6U,1U,1U);
+#define MIX_00_4_3_1_2_3_3 *output = HQX_MIX_3(w[4],w[3],w[1],2U,3U,3U);
+#define MIX_00_MIX_00_4_0_3_10 *output = HQX_MIX_3(w[4],w[3],w[1],14U,1U,1U);
+
+#define MIX_01_4 *(output + 1) = w[4];
+#define MIX_01_4_2_3_1 *(output + 1) = HQX_MIX_2(w[4],w[2],3U,1U);
+#define MIX_01_4_1_3_1 *(output + 1) = HQX_MIX_2(w[4],w[1],3U,1U);
+#define MIX_01_1_4_3_1 *(output + 1) = HQX_MIX_2(w[1],w[4],3U,1U);
+#define MIX_01_4_5_3_1 *(output + 1) = HQX_MIX_2(w[4],w[5],3U,1U);
+#define MIX_01_4_1_7_1 *(output + 1) = HQX_MIX_2(w[4],w[1],7U,1U);
+#define MIX_01_4_1_5_2_1_1 *(output + 1) = HQX_MIX_3(w[4],w[1],w[5],2U,1U,1U);
+#define MIX_01_4_2_5_2_1_1 *(output + 1) = HQX_MIX_3(w[4],w[2],w[5],2U,1U,1U);
+#define MIX_01_4_2_1_2_1_1 *(output + 1) = HQX_MIX_3(w[4],w[2],w[1],2U,1U,1U);
+#define MIX_01_4_5_1_5_2_1 *(output + 1) = HQX_MIX_3(w[4],w[5],w[1],5U,2U,1U);
+#define MIX_01_4_1_5_5_2_1 *(output + 1) = HQX_MIX_3(w[4],w[1],w[5],5U,2U,1U);
+#define MIX_01_4_1_5_6_1_1 *(output + 1) = HQX_MIX_3(w[4],w[1],w[5],6U,1U,1U);
+#define MIX_01_4_1_5_2_3_3 *(output + 1) = HQX_MIX_3(w[4],w[1],w[5],2U,3U,3U);
+#define MIX_01_4_2_3_10 *(output + 1) = HQX_MIX_3(w[4],w[1],w[5],14U,1U,1U);
+
+#define MIX_02_4 *(output + 2) = w[4];
+#define MIX_02_4_2_3_1 *(output + 2) = HQX_MIX_2(w[4],w[2],3U,1U);
+#define MIX_02_4_1_3_1 *(output + 2) = HQX_MIX_2(w[4],w[1],3U,1U);
+#define MIX_02_4_5_3_1 *(output + 2) = HQX_MIX_2(w[4],w[5],3U,1U);
+#define MIX_02_4_1_5_2_1_1 *(output + 2) = HQX_MIX_3(w[4],w[1],w[5],2U,1U,1U);
+#define MIX_02_4_1_5_2_7_7 *(output + 2) = HQX_MIX_3(w[4],w[1],w[5],2U,7U,7U);
+#define MIX_02_1_5_1_1 *(output + 2) = HQX_MIX_2(w[1],w[5],1U,1U);
+
+#define MIX_10_4 *(output + lineSize) = w[4];
+#define MIX_10_4_6_3_1 *(output + lineSize) = HQX_MIX_2(w[4],w[6],3U,1U);
+#define MIX_10_4_7_3_1 *(output + lineSize) = HQX_MIX_2(w[4],w[7],3U,1U);
+#define MIX_10_4_3_3_1 *(output + lineSize) = HQX_MIX_2(w[4],w[3],3U,1U);
+#define MIX_10_4_7_3_2_1_1 *(output + lineSize) = HQX_MIX_3(w[4],w[7],w[3],2U,1U,1U);
+#define MIX_10_4_6_3_2_1_1 *(output + lineSize) = HQX_MIX_3(w[4],w[6],w[3],2U,1U,1U);
+#define MIX_10_4_6_7_2_1_1 *(output + lineSize) = HQX_MIX_3(w[4],w[6],w[7],2U,1U,1U);
+#define MIX_10_4_3_7_5_2_1 *(output + lineSize) = HQX_MIX_3(w[4],w[3],w[7],5U,2U,1U);
+#define MIX_10_4_7_3_5_2_1 *(output + lineSize) = HQX_MIX_3(w[4],w[7],w[3],5U,2U,1U);
+#define MIX_10_4_7_3_6_1_1 *(output + lineSize) = HQX_MIX_3(w[4],w[7],w[3],6U,1U,1U);
+#define MIX_10_4_7_3_2_3_3 *(output + lineSize) = HQX_MIX_3(w[4],w[7],w[3],2U,3U,3U);
+#define MIX_10_4_6_3_10 *(output + lineSize) = HQX_MIX_3(w[4],w[7],w[3],14U,1U,1U);
+#define MIX_10_4_3_7_1 *(output + lineSize) = HQX_MIX_2(w[4],w[3],7U,1U);
+#define MIX_10_3_4_3_1 *(output + lineSize) = HQX_MIX_2(w[3],w[4],3U,1U);
+
+#define MIX_11_4 *(output + lineSize + 1) = w[4];
+#define MIX_11_4_8_3_1 *(output + lineSize + 1) = HQX_MIX_2(w[4],w[8],3U,1U);
+#define MIX_11_4_5_3_1 *(output + lineSize + 1) = HQX_MIX_2(w[4],w[5],3U,1U);
+#define MIX_11_4_7_3_1 *(output + lineSize + 1) = HQX_MIX_2(w[4],w[7],3U,1U);
+#define MIX_11_4_5_7_2_1_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[5],w[7],2U,1U,1U);
+#define MIX_11_4_8_7_2_1_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[8],w[7],2U,1U,1U);
+#define MIX_11_4_8_5_2_1_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[8],w[5],2U,1U,1U);
+#define MIX_11_4_7_5_5_2_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[7],w[5],5U,2U,1U);
+#define MIX_11_4_5_7_5_2_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[5],w[7],5U,2U,1U);
+#define MIX_11_4_5_7_6_1_1 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[5],w[7],6U,1U,1U);
+#define MIX_11_4_5_7_2_3_3 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[5],w[7],2U,3U,3U);
+#define MIX_11_4_8_3_10 *(output + lineSize + 1) = HQX_MIX_3(w[4],w[5],w[7],14U,1U,1U);
+
+#define MIX_12_4 *(output + lineSize + 2) = w[4];
+#define MIX_12_4_5_3_1 *(output + lineSize + 2) = HQX_MIX_2(w[4],w[5],3U,1U);
+#define MIX_12_4_5_7_1 *(output + lineSize + 2) = HQX_MIX_2(w[4],w[5],7U,1U);
+#define MIX_12_5_4_3_1 *(output + lineSize + 2) = HQX_MIX_2(w[5],w[4],3U,1U);
+
+#define MIX_20_4 *(output + lineSize + lineSize) = w[4];
+#define MIX_20_4_6_3_1 *(output + lineSize + lineSize) = HQX_MIX_2(w[4],w[6],3U,1U);
+#define MIX_20_4_7_3_1 *(output + lineSize + lineSize) = HQX_MIX_2(w[4],w[7],3U,1U);
+#define MIX_20_4_3_3_1 *(output + lineSize + lineSize) = HQX_MIX_2(w[4],w[3],3U,1U);
+#define MIX_20_4_7_3_2_1_1 *(output + lineSize + lineSize) = HQX_MIX_3(w[4],w[7],w[3],2U,1U,1U);
+#define MIX_20_4_7_3_2_7_7 *(output + lineSize + lineSize) = HQX_MIX_3(w[4],w[7],w[3],2U,7U,7U);
+#define MIX_20_7_3_1_1 *(output + lineSize + lineSize) = HQX_MIX_2(w[7],w[3],1U,1U);
+
+#define MIX_21_4 *(output + lineSize + lineSize + 1) = w[4];
+#define MIX_21_4_7_3_1 *(output + lineSize + lineSize + 1) = HQX_MIX_2(w[4],w[7],3U,1U);
+#define MIX_21_4_7_7_1 *(output + lineSize + lineSize + 1) = HQX_MIX_2(w[4],w[7],7U,1U);
+#define MIX_21_7_4_3_1 *(output + lineSize + lineSize + 1) = HQX_MIX_2(w[7],w[4],3U,1U);
+
+#define MIX_22_4 *(output + lineSize + lineSize + 2) = w[4];
+#define MIX_22_4_8_3_1 *(output + lineSize + lineSize + 2) = HQX_MIX_2(w[4],w[8],3U,1U);
+#define MIX_22_4_7_3_1 *(output + lineSize + lineSize + 2) = HQX_MIX_2(w[4],w[7],3U,1U);
+#define MIX_22_4_5_3_1 *(output + lineSize + lineSize + 2) = HQX_MIX_2(w[4],w[5],3U,1U);
+#define MIX_22_4_5_7_2_1_1 *(output + lineSize + lineSize + 2) = HQX_MIX_3(w[4],w[5],w[7],2U,1U,1U);
+#define MIX_22_4_5_7_2_7_7 *(output + lineSize + lineSize + 2) = HQX_MIX_3(w[4],w[5],w[7],2U,7U,7U);
+#define MIX_22_5_7_1_1 *(output + lineSize + lineSize + 2) = HQX_MIX_2(w[5],w[7],1U,1U);
+
+
+
+uint32_t *hq2x_resize(
+ const uint32_t *image,
+ uint32_t width,
+ uint32_t height,
+ uint32_t *output,
+ uint32_t trY,
+ uint32_t trU,
+ uint32_t trV,
+ uint32_t trA,
+ bool wrapX,
+ bool wrapY )
+{
+ int lineSize = width * 2;
+
+ int previous, next;
+ uint32_t w[9];
+
+ trY <<= 16;
+ trU <<= 8;
+ trA <<= 24;
+
+ // iterates between the lines
+ for (uint32_t row = 0; row < height; row++)
+ {
+ /*
+ * Note: this function uses a 3x3 sliding window over the original image.
+ *
+ * +----+----+----+
+ * | | | |
+ * | w0 | w1 | w2 |
+ * +----+----+----+
+ * | | | |
+ * | w3 | w4 | w5 |
+ * +----+----+----+
+ * | | | |
+ * | w6 | w7 | w8 |
+ * +----+----+----+
+ */
+
+ // adjusts the previous and next line pointers
+ if (row > 0)
+ previous = -width;
+ else
+ {
+ if (wrapY)
+ previous = width * (height - 1);
+ else
+ previous = 0;
+ }
+ if (row < height - 1)
+ next = width;
+ else
+ {
+ if (wrapY)
+ next = -(width * (height - 1));
+ else
+ next = 0;
+ }
+
+ // iterates between the columns
+ for (uint32_t col = 0; col < width; col++)
+ {
+ w[1] = *(image + previous);
+ w[4] = *image;
+ w[7] = *(image + next);
+
+ if (col > 0)
+ {
+ w[0] = *(image + previous - 1);
+ w[3] = *(image - 1);
+ w[6] = *(image + next - 1);
+ }
+ else
+ {
+ if (wrapX)
+ {
+ w[0] = *(image + previous + width - 1);
+ w[3] = *(image + width - 1);
+ w[6] = *(image + next + width - 1);
+ }
+ else
+ {
+ w[0] = w[1];
+ w[3] = w[4];
+ w[6] = w[7];
+ }
+ }
+
+ if (col < width - 1)
+ {
+ w[2] = *(image + previous + 1);
+ w[5] = *(image + 1);
+ w[8] = *(image + next + 1);
+ }
+ else
+ {
+ if (wrapX)
+ {
+ w[2] = *(image + previous - width + 1);
+ w[5] = *(image - width + 1);
+ w[8] = *(image + next - width + 1);
+ }
+ else
+ {
+ w[2] = w[1];
+ w[5] = w[4];
+ w[8] = w[7];
+ }
+ }
+
+ int pattern = 0;
+
+ // computes the pattern to be used considering the neighbor pixels
+ for (int k = 0, flag = 1; k < 9; k++)
+ {
+ // ignores the central pixel
+ if (k == 4) continue;
+
+ if (w[k] != w[4])
+ if (isDifferent(w[4], w[k], trY, trU, trV, trA)) pattern |= flag;
+ flag <<= 1;
+ }
+
+ switch (pattern)
+ {
+ case 0:
+ case 1:
+ case 4:
+ case 32:
+ case 128:
+ case 5:
+ case 132:
+ case 160:
+ case 33:
+ case 129:
+ case 36:
+ case 133:
+ case 164:
+ case 161:
+ case 37:
+ case 165:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 2:
+ case 34:
+ case 130:
+ case 162:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 16:
+ case 17:
+ case 48:
+ case 49:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 64:
+ case 65:
+ case 68:
+ case 69:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 8:
+ case 12:
+ case 136:
+ case 140:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 3:
+ case 35:
+ case 131:
+ case 163:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 6:
+ case 38:
+ case 134:
+ case 166:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_5_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 20:
+ case 21:
+ case 52:
+ case 53:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 144:
+ case 145:
+ case 176:
+ case 177:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 192:
+ case 193:
+ case 196:
+ case 197:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_5_3_1
+ break;
+ case 96:
+ case 97:
+ case 100:
+ case 101:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 40:
+ case 44:
+ case 168:
+ case 172:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 9:
+ case 13:
+ case 137:
+ case 141:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 18:
+ case 50:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 80:
+ case 81:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 72:
+ case 76:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 10:
+ case 138:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 66:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 24:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 7:
+ case 39:
+ case 135:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 148:
+ case 149:
+ case 180:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 224:
+ case 228:
+ case 225:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 41:
+ case 169:
+ case 45:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 22:
+ case 54:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 208:
+ case 209:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 104:
+ case 108:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 11:
+ case 139:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 19:
+ case 51:
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_00_4_3_3_1
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_00_4_1_3_5_2_1
+ MIX_01_4_1_5_2_3_3
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 146:
+ case 178:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ MIX_11_4_7_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_2_3_3
+ MIX_11_4_5_7_5_2_1
+ }
+ MIX_10_4_7_3_2_1_1
+ break;
+ case 84:
+ case 85:
+ MIX_00_4_3_1_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_01_4_1_3_1
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_01_4_5_1_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ MIX_10_4_6_3_2_1_1
+ break;
+ case 112:
+ case 113:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_10_4_3_3_1
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ break;
+ case 200:
+ case 204:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ MIX_11_4_5_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_2_3_3
+ MIX_11_4_7_5_5_2_1
+ }
+ break;
+ case 73:
+ case 77:
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_00_4_1_3_1
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_5_2_1
+ MIX_10_4_7_3_2_3_3
+ }
+ MIX_01_4_1_5_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 42:
+ case 170:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ MIX_10_4_7_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_10_4_3_7_5_2_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 14:
+ case 142:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ MIX_01_4_5_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_01_4_1_5_5_2_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 67:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 70:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_5_3_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 28:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 152:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 194:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_5_3_1
+ break;
+ case 98:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 56:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 25:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 26:
+ case 31:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 82:
+ case 214:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 88:
+ case 248:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 74:
+ case 107:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 27:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 86:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_3_1
+ break;
+ case 216:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 106:
+ MIX_00_MIX_00_4_0_3_1
+ MIX_01_4_2_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 30:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 210:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_3_1
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 120:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_3_1
+ break;
+ case 75:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 29:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 198:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_5_3_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_5_3_1
+ break;
+ case 184:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 99:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 57:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 71:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 156:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 226:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 60:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 195:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_5_3_1
+ break;
+ case 102:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_5_3_1
+ MIX_10_4_3_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 153:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 58:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 83:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 92:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 202:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 78:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 154:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 114:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 89:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 90:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 55:
+ case 23:
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_00_4_3_3_1
+ MIX_01_4
+ }
+ else
+ {
+ MIX_00_4_1_3_5_2_1
+ MIX_01_4_1_5_2_3_3
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 182:
+ case 150:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ MIX_11_4_7_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_2_3_3
+ MIX_11_4_5_7_5_2_1
+ }
+ MIX_10_4_7_3_2_1_1
+ break;
+ case 213:
+ case 212:
+ MIX_00_4_3_1_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_01_4_1_3_1
+ MIX_11_4
+ }
+ else
+ {
+ MIX_01_4_5_1_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ MIX_10_4_6_3_2_1_1
+ break;
+ case 241:
+ case 240:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_10_4_3_3_1
+ MIX_11_4
+ }
+ else
+ {
+ MIX_10_4_7_3_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ break;
+ case 236:
+ case 232:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ MIX_11_4_5_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_2_3_3
+ MIX_11_4_7_5_5_2_1
+ }
+ break;
+ case 109:
+ case 105:
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_00_4_1_3_1
+ MIX_10_4
+ }
+ else
+ {
+ MIX_00_4_3_1_5_2_1
+ MIX_10_4_7_3_2_3_3
+ }
+ MIX_01_4_1_5_2_1_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 171:
+ case 43:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ MIX_10_4_7_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_10_4_3_7_5_2_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 143:
+ case 15:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ MIX_01_4_5_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_01_4_1_5_5_2_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 124:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_3_1
+ break;
+ case 203:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_6_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 62:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 211:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_3_1
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 118:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_3_3_1
+ MIX_11_4_8_3_1
+ break;
+ case 217:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_6_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 110:
+ MIX_00_MIX_00_4_0_3_1
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 155:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 188:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 185:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 61:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 157:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 103:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_3_3_1
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 227:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 230:
+ MIX_00_4_0_3_2_1_1
+ MIX_01_4_5_3_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 199:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_6_3_2_1_1
+ MIX_11_4_5_3_1
+ break;
+ case 220:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 158:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 234:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 242:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 59:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 121:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 87:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 79:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 122:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 94:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 218:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 91:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 229:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 167:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 173:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_5_2_1_1
+ MIX_10_4_7_3_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 181:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 186:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 115:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 93:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 206:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 205:
+ case 201:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4_6_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_6_1_1
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 174:
+ case 46:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_MIX_00_4_0_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_6_1_1
+ }
+ MIX_01_4_5_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 179:
+ case 147:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4_2_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_6_1_1
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 117:
+ case 116:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4_8_3_1
+ }
+ else
+ {
+ MIX_11_4_5_7_6_1_1
+ }
+ break;
+ case 189:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 231:
+ MIX_00_4_3_3_1
+ MIX_01_4_5_3_1
+ MIX_10_4_3_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 126:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_3_1
+ break;
+ case 219:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_3_1
+ MIX_10_4_6_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 125:
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_00_4_1_3_1
+ MIX_10_4
+ }
+ else
+ {
+ MIX_00_4_3_1_5_2_1
+ MIX_10_4_7_3_2_3_3
+ }
+ MIX_01_4_1_3_1
+ MIX_11_4_8_3_1
+ break;
+ case 221:
+ MIX_00_4_1_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_01_4_1_3_1
+ MIX_11_4
+ }
+ else
+ {
+ MIX_01_4_5_1_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ MIX_10_4_6_3_1
+ break;
+ case 207:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ MIX_01_4_5_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_01_4_1_5_5_2_1
+ }
+ MIX_10_4_6_3_1
+ MIX_11_4_5_3_1
+ break;
+ case 238:
+ MIX_00_MIX_00_4_0_3_1
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ MIX_11_4_5_3_1
+ }
+ else
+ {
+ MIX_10_4_7_3_2_3_3
+ MIX_11_4_7_5_5_2_1
+ }
+ break;
+ case 190:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ MIX_11_4_7_3_1
+ }
+ else
+ {
+ MIX_01_4_1_5_2_3_3
+ MIX_11_4_5_7_5_2_1
+ }
+ MIX_10_4_7_3_1
+ break;
+ case 187:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ MIX_10_4_7_3_1
+ }
+ else
+ {
+ MIX_00_4_3_1_2_3_3
+ MIX_10_4_3_7_5_2_1
+ }
+ MIX_01_4_2_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 243:
+ MIX_00_4_3_3_1
+ MIX_01_4_2_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_10_4_3_3_1
+ MIX_11_4
+ }
+ else
+ {
+ MIX_10_4_7_3_5_2_1
+ MIX_11_4_5_7_2_3_3
+ }
+ break;
+ case 119:
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_00_4_3_3_1
+ MIX_01_4
+ }
+ else
+ {
+ MIX_00_4_1_3_5_2_1
+ MIX_01_4_1_5_2_3_3
+ }
+ MIX_10_4_3_3_1
+ MIX_11_4_8_3_1
+ break;
+ case 237:
+ case 233:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 175:
+ case 47:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ MIX_01_4_5_3_1
+ MIX_10_4_7_3_1
+ MIX_11_4_5_7_2_1_1
+ break;
+ case 183:
+ case 151:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_7_3_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 245:
+ case 244:
+ MIX_00_4_3_1_2_1_1
+ MIX_01_4_1_3_1
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 250:
+ MIX_00_MIX_00_4_0_3_1
+ MIX_01_4_2_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 123:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_3_1
+ break;
+ case 95:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_3_1
+ MIX_11_4_8_3_1
+ break;
+ case 222:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_6_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 252:
+ MIX_00_4_0_1_2_1_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 249:
+ MIX_00_4_1_3_1
+ MIX_01_4_2_1_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 235:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_5_2_1_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 111:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_5_2_1_1
+ break;
+ case 63:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_8_7_2_1_1
+ break;
+ case 159:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_6_7_2_1_1
+ MIX_11_4_7_3_1
+ break;
+ case 215:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_6_3_2_1_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 246:
+ MIX_00_4_0_3_2_1_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 254:
+ MIX_00_MIX_00_4_0_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 253:
+ MIX_00_4_1_3_1
+ MIX_01_4_1_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 251:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ MIX_01_4_2_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 239:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ MIX_01_4_5_3_1
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_6_3_10
+ }
+ MIX_11_4_5_3_1
+ break;
+ case 127:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_1_5_2_1_1
+ }
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ {
+ MIX_10_4
+ }
+ else
+ {
+ MIX_10_4_7_3_2_1_1
+ }
+ MIX_11_4_8_3_1
+ break;
+ case 191:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_MIX_00_4_0_3_10
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_7_3_1
+ MIX_11_4_7_3_1
+ break;
+ case 223:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ {
+ MIX_00_4
+ }
+ else
+ {
+ MIX_00_4_3_1_2_1_1
+ }
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_6_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_5_7_2_1_1
+ }
+ break;
+ case 247:
+ MIX_00_4_3_3_1
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ {
+ MIX_01_4
+ }
+ else
+ {
+ MIX_01_4_2_3_10
+ }
+ MIX_10_4_3_3_1
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ {
+ MIX_11_4
+ }
+ else
+ {
+ MIX_11_4_8_3_10
+ }
+ break;
+ case 255:
+ if (isDifferent(w[3], w[1], trY, trU, trV, trA))
+ MIX_00_4
+ else
+ MIX_00_MIX_00_4_0_3_10
+
+ if (isDifferent(w[1], w[5], trY, trU, trV, trA))
+ MIX_01_4
+ else
+ MIX_01_4_2_3_10
+
+ if (isDifferent(w[7], w[3], trY, trU, trV, trA))
+ MIX_10_4
+ else
+ MIX_10_4_6_3_10
+
+ if (isDifferent(w[5], w[7], trY, trU, trV, trA))
+ MIX_11_4
+ else
+ MIX_11_4_8_3_10
+ break;
+ }
+ image++;
+ output += 2;
+ }
+ output += lineSize;
+ }
+
+ return output;
+}
diff --git a/thirdparty/misc/hq2x.h b/thirdparty/misc/hq2x.h
new file mode 100644
index 0000000000..8f119d2a01
--- /dev/null
+++ b/thirdparty/misc/hq2x.h
@@ -0,0 +1,19 @@
+#ifndef HQ2X_H
+#define HQ2X_H
+
+#include "typedefs.h"
+
+
+uint32_t *hq2x_resize(
+ const uint32_t *image,
+ uint32_t width,
+ uint32_t height,
+ uint32_t *output,
+ uint32_t trY = 0x30,
+ uint32_t trU = 0x07,
+ uint32_t trV = 0x06,
+ uint32_t trA = 0x50,
+ bool wrapX = false,
+ bool wrapY = false );
+
+#endif // HQ2X_H
diff --git a/thirdparty/misc/md5.cpp b/thirdparty/misc/md5.cpp
new file mode 100644
index 0000000000..1653ab0be5
--- /dev/null
+++ b/thirdparty/misc/md5.cpp
@@ -0,0 +1,267 @@
+/*
+ **********************************************************************
+ ** md5.c **
+ ** RSA Data Security, Inc. MD5 Message Digest Algorithm **
+ ** Created: 2/17/90 RLR **
+ ** Revised: 1/91 SRD,AJ,BSK,JT Reference C Version **
+ **********************************************************************
+ */
+
+/*
+ **********************************************************************
+ ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. **
+ ** **
+ ** License to copy and use this software is granted provided that **
+ ** it is identified as the "RSA Data Security, Inc. MD5 Message **
+ ** Digest Algorithm" in all material mentioning or referencing this **
+ ** software or this function. **
+ ** **
+ ** License is also granted to make and use derivative works **
+ ** provided that such works are identified as "derived from the RSA **
+ ** Data Security, Inc. MD5 Message Digest Algorithm" in all **
+ ** material mentioning or referencing the derived work. **
+ ** **
+ ** RSA Data Security, Inc. makes no representations concerning **
+ ** either the merchantability of this software or the suitability **
+ ** of this software for any particular purpose. It is provided "as **
+ ** is" without express or implied warranty of any kind. **
+ ** **
+ ** These notices must be retained in any copies of any part of this **
+ ** documentation and/or software. **
+ **********************************************************************
+ */
+
+/* -- include the following line if the md5.h header file is separate -- */
+#include "md5.h"
+
+/* forward declaration */
+static void Transform (uint32_t *buf, uint32_t *in);
+
+
+static unsigned char PADDING[64] = {
+ 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
+};
+
+/* F, G and H are basic MD5 functions: selection, majority, parity */
+#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
+#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
+#define H(x, y, z) ((x) ^ (y) ^ (z))
+#define I(x, y, z) ((y) ^ ((x) | (~z)))
+
+/* ROTATE_LEFT rotates x left n bits */
+#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
+
+/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4 */
+/* Rotation is separate from addition to prevent recomputation */
+#define FF(a, b, c, d, x, s, ac) \
+ {(a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
+ (a) = ROTATE_LEFT ((a), (s)); \
+ (a) += (b); \
+ }
+#define GG(a, b, c, d, x, s, ac) \
+ {(a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
+ (a) = ROTATE_LEFT ((a), (s)); \
+ (a) += (b); \
+ }
+#define HH(a, b, c, d, x, s, ac) \
+ {(a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
+ (a) = ROTATE_LEFT ((a), (s)); \
+ (a) += (b); \
+ }
+#define II(a, b, c, d, x, s, ac) \
+ {(a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
+ (a) = ROTATE_LEFT ((a), (s)); \
+ (a) += (b); \
+ }
+
+void MD5Init (MD5_CTX *mdContext)
+{
+ mdContext->i[0] = mdContext->i[1] = (uint32_t)0;
+
+ /* Load magic initialization constants.
+ */
+ mdContext->buf[0] = (uint32_t)0x67452301;
+ mdContext->buf[1] = (uint32_t)0xefcdab89;
+ mdContext->buf[2] = (uint32_t)0x98badcfe;
+ mdContext->buf[3] = (uint32_t)0x10325476;
+}
+
+void MD5Update (MD5_CTX *mdContext,unsigned char *inBuf,unsigned int inLen) {
+ uint32_t in[16];
+ int mdi;
+ unsigned int i, ii;
+
+ /* compute number of bytes mod 64 */
+ mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
+
+ /* update number of bits */
+ if ((mdContext->i[0] + ((uint32_t)inLen << 3)) < mdContext->i[0])
+ mdContext->i[1]++;
+ mdContext->i[0] += ((uint32_t)inLen << 3);
+ mdContext->i[1] += ((uint32_t)inLen >> 29);
+
+ while (inLen--) {
+ /* add new character to buffer, increment mdi */
+ mdContext->in[mdi++] = *inBuf++;
+
+ /* transform if necessary */
+ if (mdi == 0x40) {
+ for (i = 0, ii = 0; i < 16; i++, ii += 4)
+ in[i] = (((uint32_t)mdContext->in[ii+3]) << 24) |
+ (((uint32_t)mdContext->in[ii+2]) << 16) |
+ (((uint32_t)mdContext->in[ii+1]) << 8) |
+ ((uint32_t)mdContext->in[ii]);
+ Transform (mdContext->buf, in);
+ mdi = 0;
+ }
+ }
+}
+
+void MD5Final (MD5_CTX *mdContext) {
+ uint32_t in[16];
+ int mdi;
+ unsigned int i, ii;
+ unsigned int padLen;
+
+ /* save number of bits */
+ in[14] = mdContext->i[0];
+ in[15] = mdContext->i[1];
+
+ /* compute number of bytes mod 64 */
+ mdi = (int)((mdContext->i[0] >> 3) & 0x3F);
+
+ /* pad out to 56 mod 64 */
+ padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi);
+ MD5Update (mdContext, PADDING, padLen);
+
+ /* append length in bits and transform */
+ for (i = 0, ii = 0; i < 14; i++, ii += 4)
+ in[i] = (((uint32_t)mdContext->in[ii+3]) << 24) |
+ (((uint32_t)mdContext->in[ii+2]) << 16) |
+ (((uint32_t)mdContext->in[ii+1]) << 8) |
+ ((uint32_t)mdContext->in[ii]);
+ Transform (mdContext->buf, in);
+
+ /* store buffer in digest */
+ for (i = 0, ii = 0; i < 4; i++, ii += 4) {
+ mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF);
+ mdContext->digest[ii+1] =
+ (unsigned char)((mdContext->buf[i] >> 8) & 0xFF);
+ mdContext->digest[ii+2] =
+ (unsigned char)((mdContext->buf[i] >> 16) & 0xFF);
+ mdContext->digest[ii+3] =
+ (unsigned char)((mdContext->buf[i] >> 24) & 0xFF);
+ }
+}
+
+/* Basic MD5 step. Transform buf based on in.
+ */
+static void Transform (uint32_t *buf, uint32_t *in) {
+ uint32_t a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+ /* Round 1 */
+#define S11 7
+#define S12 12
+#define S13 17
+#define S14 22
+ FF ( a, b, c, d, in[ 0], S11, 3614090360); /* 1 */
+ FF ( d, a, b, c, in[ 1], S12, 3905402710); /* 2 */
+ FF ( c, d, a, b, in[ 2], S13, 606105819); /* 3 */
+ FF ( b, c, d, a, in[ 3], S14, 3250441966); /* 4 */
+ FF ( a, b, c, d, in[ 4], S11, 4118548399); /* 5 */
+ FF ( d, a, b, c, in[ 5], S12, 1200080426); /* 6 */
+ FF ( c, d, a, b, in[ 6], S13, 2821735955); /* 7 */
+ FF ( b, c, d, a, in[ 7], S14, 4249261313); /* 8 */
+ FF ( a, b, c, d, in[ 8], S11, 1770035416); /* 9 */
+ FF ( d, a, b, c, in[ 9], S12, 2336552879); /* 10 */
+ FF ( c, d, a, b, in[10], S13, 4294925233); /* 11 */
+ FF ( b, c, d, a, in[11], S14, 2304563134); /* 12 */
+ FF ( a, b, c, d, in[12], S11, 1804603682); /* 13 */
+ FF ( d, a, b, c, in[13], S12, 4254626195); /* 14 */
+ FF ( c, d, a, b, in[14], S13, 2792965006); /* 15 */
+ FF ( b, c, d, a, in[15], S14, 1236535329); /* 16 */
+
+ /* Round 2 */
+#define S21 5
+#define S22 9
+#define S23 14
+#define S24 20
+ GG ( a, b, c, d, in[ 1], S21, 4129170786); /* 17 */
+ GG ( d, a, b, c, in[ 6], S22, 3225465664); /* 18 */
+ GG ( c, d, a, b, in[11], S23, 643717713); /* 19 */
+ GG ( b, c, d, a, in[ 0], S24, 3921069994); /* 20 */
+ GG ( a, b, c, d, in[ 5], S21, 3593408605); /* 21 */
+ GG ( d, a, b, c, in[10], S22, 38016083); /* 22 */
+ GG ( c, d, a, b, in[15], S23, 3634488961); /* 23 */
+ GG ( b, c, d, a, in[ 4], S24, 3889429448); /* 24 */
+ GG ( a, b, c, d, in[ 9], S21, 568446438); /* 25 */
+ GG ( d, a, b, c, in[14], S22, 3275163606); /* 26 */
+ GG ( c, d, a, b, in[ 3], S23, 4107603335); /* 27 */
+ GG ( b, c, d, a, in[ 8], S24, 1163531501); /* 28 */
+ GG ( a, b, c, d, in[13], S21, 2850285829); /* 29 */
+ GG ( d, a, b, c, in[ 2], S22, 4243563512); /* 30 */
+ GG ( c, d, a, b, in[ 7], S23, 1735328473); /* 31 */
+ GG ( b, c, d, a, in[12], S24, 2368359562); /* 32 */
+
+ /* Round 3 */
+#define S31 4
+#define S32 11
+#define S33 16
+#define S34 23
+ HH ( a, b, c, d, in[ 5], S31, 4294588738); /* 33 */
+ HH ( d, a, b, c, in[ 8], S32, 2272392833); /* 34 */
+ HH ( c, d, a, b, in[11], S33, 1839030562); /* 35 */
+ HH ( b, c, d, a, in[14], S34, 4259657740); /* 36 */
+ HH ( a, b, c, d, in[ 1], S31, 2763975236); /* 37 */
+ HH ( d, a, b, c, in[ 4], S32, 1272893353); /* 38 */
+ HH ( c, d, a, b, in[ 7], S33, 4139469664); /* 39 */
+ HH ( b, c, d, a, in[10], S34, 3200236656); /* 40 */
+ HH ( a, b, c, d, in[13], S31, 681279174); /* 41 */
+ HH ( d, a, b, c, in[ 0], S32, 3936430074); /* 42 */
+ HH ( c, d, a, b, in[ 3], S33, 3572445317); /* 43 */
+ HH ( b, c, d, a, in[ 6], S34, 76029189); /* 44 */
+ HH ( a, b, c, d, in[ 9], S31, 3654602809); /* 45 */
+ HH ( d, a, b, c, in[12], S32, 3873151461); /* 46 */
+ HH ( c, d, a, b, in[15], S33, 530742520); /* 47 */
+ HH ( b, c, d, a, in[ 2], S34, 3299628645); /* 48 */
+
+ /* Round 4 */
+#define S41 6
+#define S42 10
+#define S43 15
+#define S44 21
+ II ( a, b, c, d, in[ 0], S41, 4096336452); /* 49 */
+ II ( d, a, b, c, in[ 7], S42, 1126891415); /* 50 */
+ II ( c, d, a, b, in[14], S43, 2878612391); /* 51 */
+ II ( b, c, d, a, in[ 5], S44, 4237533241); /* 52 */
+ II ( a, b, c, d, in[12], S41, 1700485571); /* 53 */
+ II ( d, a, b, c, in[ 3], S42, 2399980690); /* 54 */
+ II ( c, d, a, b, in[10], S43, 4293915773); /* 55 */
+ II ( b, c, d, a, in[ 1], S44, 2240044497); /* 56 */
+ II ( a, b, c, d, in[ 8], S41, 1873313359); /* 57 */
+ II ( d, a, b, c, in[15], S42, 4264355552); /* 58 */
+ II ( c, d, a, b, in[ 6], S43, 2734768916); /* 59 */
+ II ( b, c, d, a, in[13], S44, 1309151649); /* 60 */
+ II ( a, b, c, d, in[ 4], S41, 4149444226); /* 61 */
+ II ( d, a, b, c, in[11], S42, 3174756917); /* 62 */
+ II ( c, d, a, b, in[ 2], S43, 718787259); /* 63 */
+ II ( b, c, d, a, in[ 9], S44, 3951481745); /* 64 */
+
+ buf[0] += a;
+ buf[1] += b;
+ buf[2] += c;
+ buf[3] += d;
+}
+
+/*
+ **********************************************************************
+ ** End of md5.c **
+ ******************************* (cut) ********************************
+ */
diff --git a/thirdparty/misc/md5.h b/thirdparty/misc/md5.h
new file mode 100644
index 0000000000..e99d58b443
--- /dev/null
+++ b/thirdparty/misc/md5.h
@@ -0,0 +1,61 @@
+#ifndef MD5_H
+#define MD5_H
+
+/*
+ **********************************************************************
+ ** md5.h -- Header file for implementation of MD5 **
+ ** RSA Data Security, Inc. MD5 Message Digest Algorithm **
+ ** Created: 2/17/90 RLR **
+ ** Revised: 12/27/90 SRD,AJ,BSK,JT Reference C version **
+ ** Revised (for MD5): RLR 4/27/91 **
+ ** -- G modified to have y&~z instead of y&z **
+ ** -- FF, GG, HH modified to add in last register done **
+ ** -- Access pattern: round 2 works mod 5, round 3 works mod 3 **
+ ** -- distinct additive constant for each step **
+ ** -- round 4 added, working mod 7 **
+ **********************************************************************
+ */
+
+/*
+ **********************************************************************
+ ** Copyright (C) 1990, RSA Data Security, Inc. All rights reserved. **
+ ** **
+ ** License to copy and use this software is granted provided that **
+ ** it is identified as the "RSA Data Security, Inc. MD5 Message **
+ ** Digest Algorithm" in all material mentioning or referencing this **
+ ** software or this function. **
+ ** **
+ ** License is also granted to make and use derivative works **
+ ** provided that such works are identified as "derived from the RSA **
+ ** Data Security, Inc. MD5 Message Digest Algorithm" in all **
+ ** material mentioning or referencing the derived work. **
+ ** **
+ ** RSA Data Security, Inc. makes no representations concerning **
+ ** either the merchantability of this software or the suitability **
+ ** of this software for any particular purpose. It is provided "as **
+ ** is" without express or implied warranty of any kind. **
+ ** **
+ ** These notices must be retained in any copies of any part of this **
+ ** documentation and/or software. **
+ **********************************************************************
+ */
+
+/* NOT typedef a 32 bit type */
+
+#include "typedefs.h"
+
+/* Data structure for MD5 (Message Digest) computation */
+typedef struct {
+ uint32_t i[2]; /* number of _bits_ handled mod 2^64 */
+ uint32_t buf[4]; /* scratch buffer */
+ unsigned char in[64]; /* input buffer */
+ unsigned char digest[16]; /* actual digest after MD5Final call */
+} MD5_CTX;
+
+void MD5Init (MD5_CTX *mdContext);
+void MD5Update (MD5_CTX *mdContext,unsigned char *inBuf,unsigned int inLen);
+void MD5Final (MD5_CTX *mdContext);
+
+
+
+#endif // MD5_H
diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp
new file mode 100644
index 0000000000..eac3b36d36
--- /dev/null
+++ b/thirdparty/misc/pcg.cpp
@@ -0,0 +1,15 @@
+// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
+// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
+
+#include "pcg.h"
+
+uint32_t pcg32_random_r(pcg32_random_t* rng)
+{
+ uint64_t oldstate = rng->state;
+ // Advance internal state
+ rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
+ // Calculate output function (XSH RR), uses old state for max ILP
+ uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
+ uint32_t rot = oldstate >> 59u;
+ return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
+}
diff --git a/thirdparty/misc/pcg.h b/thirdparty/misc/pcg.h
new file mode 100644
index 0000000000..81f4c9770e
--- /dev/null
+++ b/thirdparty/misc/pcg.h
@@ -0,0 +1,14 @@
+// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
+// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
+
+#ifndef RANDOM_H
+#define RANDOM_H
+
+#include "typedefs.h"
+
+#define PCG_DEFAULT_INC_64 1442695040888963407ULL
+
+typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
+uint32_t pcg32_random_r(pcg32_random_t* rng);
+
+#endif // RANDOM_H
diff --git a/thirdparty/misc/sha256.c b/thirdparty/misc/sha256.c
new file mode 100644
index 0000000000..68a4339af9
--- /dev/null
+++ b/thirdparty/misc/sha256.c
@@ -0,0 +1,245 @@
+/*
+* SHA-256 implementation.
+*
+* Copyright (c) 2010 Ilya O. Levin, http://www.literatecode.com
+*
+* Permission to use, copy, modify, and distribute this software for any
+* purpose with or without fee is hereby granted, provided that the above
+* copyright notice and this permission notice appear in all copies.
+*
+* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+#define SWAP_BYTES
+// #define USE_STD_MEMCPY
+// #define SELF_TEST
+
+#ifdef USE_STD_MEMCPY
+#include <string.h>
+#endif
+#include "sha256.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define RL(x,n) (((x) << n) | ((x) >> (32 - n)))
+#define RR(x,n) (((x) >> n) | ((x) << (32 - n)))
+
+#define S0(x) (RR((x), 2) ^ RR((x),13) ^ RR((x),22))
+#define S1(x) (RR((x), 6) ^ RR((x),11) ^ RR((x),25))
+#define G0(x) (RR((x), 7) ^ RR((x),18) ^ ((x) >> 3))
+#define G1(x) (RR((x),17) ^ RR((x),19) ^ ((x) >> 10))
+
+#ifdef SWAP_BYTES
+#define BSWP(x,y) _bswapw((uint32_t *)(x), (uint32_t)(y))
+#else
+#define BSWP(p,n)
+#endif
+#ifdef USE_STD_MEMCPY
+#define MEMCP(x,y,z) memcpy((x),(y),(z))
+#else
+#define MEMCP(x,y,z) _memcp((x),(y),(z))
+#endif
+
+#ifndef __cdecl
+#define __cdecl
+#endif
+
+static const uint32_t K[64] = {
+ 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
+ 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
+ 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
+ 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
+ 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
+ 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
+ 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
+ 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
+ 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
+ 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
+ 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
+ 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
+ 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
+ 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
+ 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
+ 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
+};
+
+/* -------------------------------------------------------------------------- */
+static void _bswapw(uint32_t *p, uint32_t i)
+{
+ while (i--) p[i] = (RR(p[i],24) & 0x00ff00ff) | (RR(p[i],8) & 0xff00ff00);
+
+} /* _bswapw */
+
+/* -------------------------------------------------------------------------- */
+#ifndef USE_STD_MEMCPY
+void * __cdecl _memcp (void *d, const void *s, uint32_t sz)
+{
+ void *rv = d;
+
+ while (sz--) *(char *)d = *(char *)s, d = (char *)d + 1, s = (char *)s + 1;
+
+ return(rv);
+} /* _memcp */
+#endif
+
+/* -------------------------------------------------------------------------- */
+static void _rtrf(uint32_t *b, uint32_t *p, uint32_t i, uint32_t j)
+{
+ #define B(x, y) b[(x-y) & 7]
+ #define P(x, y) p[(x+y) & 15]
+
+ B(7,i) += (j ? (p[i & 15] += G1(P(i,14)) + P(i,9) + G0(P(i,1))) : p[i & 15])
+ + K[i+j] + S1(B(4,i))
+ + (B(6,i) ^ (B(4,i) & (B(5,i) ^ B(6,i))));
+ B(3,i) += B(7,i);
+ B(7,i) += S0(B(0,i)) + ( (B(0,i) & B(1,i)) | (B(2,i) & (B(0,i) ^ B(1,i))) );
+
+ #undef P
+ #undef B
+} /* _rtrf */
+
+/* -------------------------------------------------------------------------- */
+static void _hash(sha256_context *ctx)
+{
+ uint32_t b[8], *p, j;
+
+ b[0] = ctx->hash[0]; b[1] = ctx->hash[1]; b[2] = ctx->hash[2];
+ b[3] = ctx->hash[3]; b[4] = ctx->hash[4]; b[5] = ctx->hash[5];
+ b[6] = ctx->hash[6]; b[7] = ctx->hash[7];
+
+ for (p = ctx->buf, j = 0; j < 64; j += 16)
+ _rtrf(b, p, 0, j), _rtrf(b, p, 1, j), _rtrf(b, p, 2, j),
+ _rtrf(b, p, 3, j), _rtrf(b, p, 4, j), _rtrf(b, p, 5, j),
+ _rtrf(b, p, 6, j), _rtrf(b, p, 7, j), _rtrf(b, p, 8, j),
+ _rtrf(b, p, 9, j), _rtrf(b, p, 10, j), _rtrf(b, p, 11, j),
+ _rtrf(b, p, 12, j), _rtrf(b, p, 13, j), _rtrf(b, p, 14, j),
+ _rtrf(b, p, 15, j);
+
+ ctx->hash[0] += b[0]; ctx->hash[1] += b[1]; ctx->hash[2] += b[2];
+ ctx->hash[3] += b[3]; ctx->hash[4] += b[4]; ctx->hash[5] += b[5];
+ ctx->hash[6] += b[6]; ctx->hash[7] += b[7];
+
+} /* _hash */
+
+/* -------------------------------------------------------------------------- */
+void sha256_init(sha256_context ctx[1])
+{
+ ctx->len[0] = ctx->len[1] = 0;
+ ctx->hash[0] = 0x6a09e667; ctx->hash[1] = 0xbb67ae85;
+ ctx->hash[2] = 0x3c6ef372; ctx->hash[3] = 0xa54ff53a;
+ ctx->hash[4] = 0x510e527f; ctx->hash[5] = 0x9b05688c;
+ ctx->hash[6] = 0x1f83d9ab; ctx->hash[7] = 0x5be0cd19;
+
+} /* sha256_init */
+
+/* -------------------------------------------------------------------------- */
+void sha256_hash(sha256_context *ctx, uint8_t *dat, uint32_t sz)
+{
+ register uint32_t i = ctx->len[0] & 63, l, j;
+
+ if ((ctx->len[0] += sz) < sz) ++(ctx->len[1]);
+
+ for (j = 0, l = 64-i; sz >= l; j += l, sz -= l, l = 64, i = 0)
+ {
+ MEMCP(&ctx->buf[i], &dat[j], l);
+ BSWP(ctx->buf, 16 );
+ _hash(ctx);
+ }
+ MEMCP(&ctx->buf[i], &dat[j], sz);
+
+} /* _hash */
+
+/* -------------------------------------------------------------------------- */
+void sha256_done(sha256_context *ctx, uint8_t *buf)
+{
+ uint32_t i = (uint32_t)(ctx->len[0] & 63), j = ((~i) & 3) << 3;
+
+ BSWP(ctx->buf, (i + 3) >> 2);
+
+ ctx->buf[i >> 2] &= 0xffffff80 << j; /* add padding */
+ ctx->buf[i >> 2] |= 0x00000080 << j;
+
+ if (i < 56) i = (i >> 2) + 1;
+ else ctx->buf[15] ^= (i < 60) ? ctx->buf[15] : 0, _hash(ctx), i = 0;
+
+ while (i < 14) ctx->buf[i++] = 0;
+
+ ctx->buf[14] = (ctx->len[1] << 3)|(ctx->len[0] >> 29); /* add length */
+ ctx->buf[15] = ctx->len[0] << 3;
+
+ _hash(ctx);
+
+ for (i = 0; i < 32; i++)
+ ctx->buf[i % 16] = 0, /* may remove this line in case of a DIY cleanup */
+ buf[i] = (uint8_t)(ctx->hash[i >> 2] >> ((~i & 3) << 3));
+
+} /* sha256_done */
+
+
+#ifdef SELF_TEST
+#pragma warning (push, 0)
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#pragma warning(pop)
+
+char *buf[] = {
+ "",
+ "e3b0c442 98fc1c14 9afbf4c8 996fb924 27ae41e4 649b934c a495991b 7852b855",
+
+ "abc",
+ "ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad",
+
+ "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
+ "248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1",
+
+ "The quick brown fox jumps over the lazy dog",
+ "d7a8fbb3 07d78094 69ca9abc b0082e4f 8d5651e4 6d3cdb76 2d02d0bf 37c9e592",
+
+ "The quick brown fox jumps over the lazy cog", /* avalanche effect test */
+ "e4c4d8f3 bf76b692 de791a17 3e053211 50f7a345 b46484fe 427f6acc 7ecc81be",
+
+ "bhn5bjmoniertqea40wro2upyflkydsibsk8ylkmgbvwi420t44cq034eou1szc1k0mk46oeb7ktzmlxqkbte2sy",
+ "9085df2f 02e0cc45 5928d0f5 1b27b4bf 1d9cd260 a66ed1fd a11b0a3f f5756d99"
+};
+
+int main(int argc, char *argv[])
+{
+ sha256_context ctx;
+ uint8_t hv[32];
+ uint32_t i, j;
+
+ for (j = 0; j < (sizeof(buf)/sizeof(buf[0])); j += 2)
+ {
+ sha256_init(&ctx);
+ sha256_hash(&ctx, (uint8_t *)buf[j], (uint32_t)strlen(buf[j]));
+ sha256_done(&ctx, hv);
+ printf("input = %s\ndigest: %s\nresult: ", buf[j], buf[j+1]);
+ for (i = 0; i < 32; i++) printf("%02x%s", hv[i], ((i%4)==3)?" ":"");
+ printf("\n\n");
+ }
+
+ for (j = 1; j < (uint32_t)argc; j++)
+ {
+ printf("argv[%d]: %s\nresult: ", (int)j, argv[j]);
+ sha256_init(&ctx);
+ sha256_hash(&ctx, (uint8_t *)argv[j], (uint32_t)strlen(argv[j]));
+ sha256_done(&ctx, hv);
+ for (i = 0; i < 32; i++) printf("%02x%s", hv[i], ((i%4)==3)?" ":"");
+ printf("\n\n");
+ }
+
+ return 0;
+} /* main */
+#endif
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/thirdparty/misc/sha256.h b/thirdparty/misc/sha256.h
new file mode 100644
index 0000000000..e19e56b4cc
--- /dev/null
+++ b/thirdparty/misc/sha256.h
@@ -0,0 +1,50 @@
+/*
+* SHA-256 implementation.
+*
+* Copyright (c) 2010 Ilya O. Levin, http://www.literatecode.com
+*
+* Permission to use, copy, modify, and distribute this software for any
+* purpose with or without fee is hereby granted, provided that the above
+* copyright notice and this permission notice appear in all copies.
+*
+* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+#ifdef _MSC_VER
+#ifndef uint8_t
+typedef unsigned __int8 uint8_t;
+#endif
+#ifndef uint32_t
+typedef unsigned __int32 uint32_t;
+#endif
+#ifndef uint64_t
+typedef __int64 int64_t;
+typedef unsigned __int64 uint64_t;
+#endif
+#else
+#include <stdint.h>
+#endif
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+ typedef struct {
+ uint32_t buf[16];
+ uint32_t hash[8];
+ uint32_t len[2];
+ } sha256_context;
+
+ void sha256_init(sha256_context *);
+ void sha256_hash(sha256_context *, uint8_t * /* data */, uint32_t /* len */);
+ void sha256_done(sha256_context *, uint8_t * /* hash */);
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/thirdparty/misc/triangulator.cpp b/thirdparty/misc/triangulator.cpp
new file mode 100644
index 0000000000..75b2b064c4
--- /dev/null
+++ b/thirdparty/misc/triangulator.cpp
@@ -0,0 +1,1550 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//Permission is hereby granted, free of charge, to any person obtaining a copy
+//of this software and associated documentation files (the "Software"), to deal
+//in the Software without restriction, including without limitation the rights
+//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+//copies of the Software, and to permit persons to whom the Software is
+//furnished to do so, subject to the following conditions:
+//
+//The above copyright notice and this permission notice shall be included in
+//all copies or substantial portions of the Software.
+//
+//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+//THE SOFTWARE.
+
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#include "triangulator.h"
+
+
+#define TRIANGULATOR_VERTEXTYPE_REGULAR 0
+#define TRIANGULATOR_VERTEXTYPE_START 1
+#define TRIANGULATOR_VERTEXTYPE_END 2
+#define TRIANGULATOR_VERTEXTYPE_SPLIT 3
+#define TRIANGULATOR_VERTEXTYPE_MERGE 4
+
+TriangulatorPoly::TriangulatorPoly() {
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+TriangulatorPoly::~TriangulatorPoly() {
+ if(points) delete [] points;
+}
+
+void TriangulatorPoly::Clear() {
+ if(points) delete [] points;
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+void TriangulatorPoly::Init(long numpoints) {
+ Clear();
+ this->numpoints = numpoints;
+ points = new Vector2[numpoints];
+}
+
+void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) {
+ Init(3);
+ points[0] = p1;
+ points[1] = p2;
+ points[2] = p3;
+}
+
+TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) {
+ hole = src.hole;
+ numpoints = src.numpoints;
+ points = new Vector2[numpoints];
+ memcpy(points, src.points, numpoints*sizeof(Vector2));
+}
+
+TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) {
+ Clear();
+ hole = src.hole;
+ numpoints = src.numpoints;
+ points = new Vector2[numpoints];
+ memcpy(points, src.points, numpoints*sizeof(Vector2));
+ return *this;
+}
+
+int TriangulatorPoly::GetOrientation() {
+ long i1,i2;
+ real_t area = 0;
+ for(i1=0; i1<numpoints; i1++) {
+ i2 = i1+1;
+ if(i2 == numpoints) i2 = 0;
+ area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
+ }
+ if(area>0) return TRIANGULATOR_CCW;
+ if(area<0) return TRIANGULATOR_CW;
+ return 0;
+}
+
+void TriangulatorPoly::SetOrientation(int orientation) {
+ int polyorientation = GetOrientation();
+ if(polyorientation&&(polyorientation!=orientation)) {
+ Invert();
+ }
+}
+
+void TriangulatorPoly::Invert() {
+ long i;
+ Vector2 *invpoints;
+
+ invpoints = new Vector2[numpoints];
+ for(i=0;i<numpoints;i++) {
+ invpoints[i] = points[numpoints-i-1];
+ }
+
+ delete [] points;
+ points = invpoints;
+}
+
+Vector2 TriangulatorPartition::Normalize(const Vector2 &p) {
+ Vector2 r;
+ real_t n = sqrt(p.x*p.x + p.y*p.y);
+ if(n!=0) {
+ r = p/n;
+ } else {
+ r.x = 0;
+ r.y = 0;
+ }
+ return r;
+}
+
+real_t TriangulatorPartition::Distance(const Vector2 &p1, const Vector2 &p2) {
+ real_t dx,dy;
+ dx = p2.x - p1.x;
+ dy = p2.y - p1.y;
+ return(sqrt(dx*dx + dy*dy));
+}
+
+//checks if two lines intersect
+int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22) {
+ if((p11.x == p21.x)&&(p11.y == p21.y)) return 0;
+ if((p11.x == p22.x)&&(p11.y == p22.y)) return 0;
+ if((p12.x == p21.x)&&(p12.y == p21.y)) return 0;
+ if((p12.x == p22.x)&&(p12.y == p22.y)) return 0;
+
+ Vector2 v1ort,v2ort,v;
+ real_t dot11,dot12,dot21,dot22;
+
+ v1ort.x = p12.y-p11.y;
+ v1ort.y = p11.x-p12.x;
+
+ v2ort.x = p22.y-p21.y;
+ v2ort.y = p21.x-p22.x;
+
+ v = p21-p11;
+ dot21 = v.x*v1ort.x + v.y*v1ort.y;
+ v = p22-p11;
+ dot22 = v.x*v1ort.x + v.y*v1ort.y;
+
+ v = p11-p21;
+ dot11 = v.x*v2ort.x + v.y*v2ort.y;
+ v = p12-p21;
+ dot12 = v.x*v2ort.x + v.y*v2ort.y;
+
+ if(dot11*dot12>0) return 0;
+ if(dot21*dot22>0) return 0;
+
+ return 1;
+}
+
+//removes holes from inpolys by merging them with non-holes
+int TriangulatorPartition::RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys) {
+ List<TriangulatorPoly> polys;
+ List<TriangulatorPoly>::Element *holeiter,*polyiter,*iter,*iter2;
+ long i,i2,holepointindex,polypointindex;
+ Vector2 holepoint,polypoint,bestpolypoint;
+ Vector2 linep1,linep2;
+ Vector2 v1,v2;
+ TriangulatorPoly newpoly;
+ bool hasholes;
+ bool pointvisible;
+ bool pointfound;
+
+ //check for trivial case (no holes)
+ hasholes = false;
+ for(iter = inpolys->front(); iter; iter=iter->next()) {
+ if(iter->get().IsHole()) {
+ hasholes = true;
+ break;
+ }
+ }
+ if(!hasholes) {
+ for(iter = inpolys->front(); iter; iter=iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+ return 1;
+ }
+
+ polys = *inpolys;
+
+ while(1) {
+ //find the hole point with the largest x
+ hasholes = false;
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ if(!iter->get().IsHole()) continue;
+
+ if(!hasholes) {
+ hasholes = true;
+ holeiter = iter;
+ holepointindex = 0;
+ }
+
+ for(i=0; i < iter->get().GetNumPoints(); i++) {
+ if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) {
+ holeiter = iter;
+ holepointindex = i;
+ }
+ }
+ }
+ if(!hasholes) break;
+ holepoint = holeiter->get().GetPoint(holepointindex);
+
+ pointfound = false;
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ if(iter->get().IsHole()) continue;
+ for(i=0; i < iter->get().GetNumPoints(); i++) {
+ if(iter->get().GetPoint(i).x <= holepoint.x) continue;
+ if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())),
+ iter->get().GetPoint(i),
+ iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())),
+ holepoint))
+ continue;
+ polypoint = iter->get().GetPoint(i);
+ if(pointfound) {
+ v1 = Normalize(polypoint-holepoint);
+ v2 = Normalize(bestpolypoint-holepoint);
+ if(v2.x > v1.x) continue;
+ }
+ pointvisible = true;
+ for(iter2 = polys.front(); iter2; iter2=iter2->next()) {
+ if(iter2->get().IsHole()) continue;
+ for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) {
+ linep1 = iter2->get().GetPoint(i2);
+ linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints()));
+ if(Intersects(holepoint,polypoint,linep1,linep2)) {
+ pointvisible = false;
+ break;
+ }
+ }
+ if(!pointvisible) break;
+ }
+ if(pointvisible) {
+ pointfound = true;
+ bestpolypoint = polypoint;
+ polyiter = iter;
+ polypointindex = i;
+ }
+ }
+ }
+
+ if(!pointfound) return 0;
+
+ newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2);
+ i2 = 0;
+ for(i=0;i<=polypointindex;i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+ for(i=0;i<=holeiter->get().GetNumPoints();i++) {
+ newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints());
+ i2++;
+ }
+ for(i=polypointindex;i<polyiter->get().GetNumPoints();i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+
+ polys.erase(holeiter);
+ polys.erase(polyiter);
+ polys.push_back(newpoly);
+ }
+
+ for(iter = polys.front(); iter; iter=iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+
+ return 1;
+}
+
+bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp>0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp<0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) {
+ if(IsConvex(p1,p,p2)) return false;
+ if(IsConvex(p2,p,p3)) return false;
+ if(IsConvex(p3,p,p1)) return false;
+ return true;
+}
+
+bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) {
+ bool convex;
+
+ convex = IsConvex(p1,p2,p3);
+
+ if(convex) {
+ if(!IsConvex(p1,p2,p)) return false;
+ if(!IsConvex(p2,p3,p)) return false;
+ return true;
+ } else {
+ if(IsConvex(p1,p2,p)) return true;
+ if(IsConvex(p2,p3,p)) return true;
+ return false;
+ }
+}
+
+bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) {
+ Vector2 p1,p2,p3;
+
+ p1 = v->previous->p;
+ p2 = v->p;
+ p3 = v->next->p;
+
+ return InCone(p1,p2,p3,p);
+}
+
+void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) {
+ PartitionVertex *v1,*v3;
+ v1 = v->previous;
+ v3 = v->next;
+ v->isConvex = !IsReflex(v1->p,v->p,v3->p);
+}
+
+void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) {
+ long i;
+ PartitionVertex *v1,*v3;
+ Vector2 vec1,vec3;
+
+ v1 = v->previous;
+ v3 = v->next;
+
+ v->isConvex = IsConvex(v1->p,v->p,v3->p);
+
+ vec1 = Normalize(v1->p - v->p);
+ vec3 = Normalize(v3->p - v->p);
+ v->angle = vec1.x*vec3.x + vec1.y*vec3.y;
+
+ if(v->isConvex) {
+ v->isEar = true;
+ for(i=0;i<numvertices;i++) {
+ if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue;
+ if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue;
+ if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue;
+ if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) {
+ v->isEar = false;
+ break;
+ }
+ }
+ } else {
+ v->isEar = false;
+ }
+}
+
+//triangulation by ear removal
+int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ long numvertices;
+ PartitionVertex *vertices;
+ PartitionVertex *ear;
+ TriangulatorPoly triangle;
+ long i,j;
+ bool earfound;
+
+ if(poly->GetNumPoints() < 3) return 0;
+ if(poly->GetNumPoints() == 3) {
+ triangles->push_back(*poly);
+ return 1;
+ }
+
+ numvertices = poly->GetNumPoints();
+
+ vertices = new PartitionVertex[numvertices];
+ for(i=0;i<numvertices;i++) {
+ vertices[i].isActive = true;
+ vertices[i].p = poly->GetPoint(i);
+ if(i==(numvertices-1)) vertices[i].next=&(vertices[0]);
+ else vertices[i].next=&(vertices[i+1]);
+ if(i==0) vertices[i].previous = &(vertices[numvertices-1]);
+ else vertices[i].previous = &(vertices[i-1]);
+ }
+ for(i=0;i<numvertices;i++) {
+ UpdateVertex(&vertices[i],vertices,numvertices);
+ }
+
+ for(i=0;i<numvertices-3;i++) {
+ earfound = false;
+ //find the most extruded ear
+ for(j=0;j<numvertices;j++) {
+ if(!vertices[j].isActive) continue;
+ if(!vertices[j].isEar) continue;
+ if(!earfound) {
+ earfound = true;
+ ear = &(vertices[j]);
+ } else {
+ if(vertices[j].angle > ear->angle) {
+ ear = &(vertices[j]);
+ }
+ }
+ }
+ if(!earfound) {
+ delete [] vertices;
+ return 0;
+ }
+
+ triangle.Triangle(ear->previous->p,ear->p,ear->next->p);
+ triangles->push_back(triangle);
+
+ ear->isActive = false;
+ ear->previous->next = ear->next;
+ ear->next->previous = ear->previous;
+
+ if(i==numvertices-4) break;
+
+ UpdateVertex(ear->previous,vertices,numvertices);
+ UpdateVertex(ear->next,vertices,numvertices);
+ }
+ for(i=0;i<numvertices;i++) {
+ if(vertices[i].isActive) {
+ triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p);
+ triangles->push_back(triangle);
+ break;
+ }
+ }
+
+ delete [] vertices;
+
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> outpolys;
+ List<TriangulatorPoly>::Element*iter;
+
+ if(!RemoveHoles(inpolys,&outpolys)) return 0;
+ for(iter=outpolys.front();iter;iter=iter->next()) {
+ if(!Triangulate_EC(&(iter->get()),triangles)) return 0;
+ }
+ return 1;
+}
+
+int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
+ List<TriangulatorPoly> triangles;
+ List<TriangulatorPoly>::Element *iter1,*iter2;
+ TriangulatorPoly *poly1,*poly2;
+ TriangulatorPoly newpoly;
+ Vector2 d1,d2,p1,p2,p3;
+ long i11,i12,i21,i22,i13,i23,j,k;
+ bool isdiagonal;
+ long numreflex;
+
+ //check if the poly is already convex
+ numreflex = 0;
+ for(i11=0;i11<poly->GetNumPoints();i11++) {
+ if(i11==0) i12 = poly->GetNumPoints()-1;
+ else i12=i11-1;
+ if(i11==(poly->GetNumPoints()-1)) i13=0;
+ else i13=i11+1;
+ if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) {
+ numreflex = 1;
+ break;
+ }
+ }
+ if(numreflex == 0) {
+ parts->push_back(*poly);
+ return 1;
+ }
+
+ if(!Triangulate_EC(poly,&triangles)) return 0;
+
+ for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
+ poly1 = &(iter1->get());
+ for(i11=0;i11<poly1->GetNumPoints();i11++) {
+ d1 = poly1->GetPoint(i11);
+ i12 = (i11+1)%(poly1->GetNumPoints());
+ d2 = poly1->GetPoint(i12);
+
+ isdiagonal = false;
+ for(iter2 = iter1; iter2 ; iter2=iter2->next()) {
+ if(iter1 == iter2) continue;
+ poly2 = &(iter2->get());
+
+ for(i21=0;i21<poly2->GetNumPoints();i21++) {
+ if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue;
+ i22 = (i21+1)%(poly2->GetNumPoints());
+ if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue;
+ isdiagonal = true;
+ break;
+ }
+ if(isdiagonal) break;
+ }
+
+ if(!isdiagonal) continue;
+
+ p2 = poly1->GetPoint(i11);
+ if(i11 == 0) i13 = poly1->GetNumPoints()-1;
+ else i13 = i11-1;
+ p1 = poly1->GetPoint(i13);
+ if(i22 == (poly2->GetNumPoints()-1)) i23 = 0;
+ else i23 = i22+1;
+ p3 = poly2->GetPoint(i23);
+
+ if(!IsConvex(p1,p2,p3)) continue;
+
+ p2 = poly1->GetPoint(i12);
+ if(i12 == (poly1->GetNumPoints()-1)) i13 = 0;
+ else i13 = i12+1;
+ p3 = poly1->GetPoint(i13);
+ if(i21 == 0) i23 = poly2->GetNumPoints()-1;
+ else i23 = i21-1;
+ p1 = poly2->GetPoint(i23);
+
+ if(!IsConvex(p1,p2,p3)) continue;
+
+ newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2);
+ k = 0;
+ for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) {
+ newpoly[k] = poly1->GetPoint(j);
+ k++;
+ }
+ for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) {
+ newpoly[k] = poly2->GetPoint(j);
+ k++;
+ }
+
+ triangles.erase(iter2);
+ iter1->get() = newpoly;
+ poly1 = &(iter1->get());
+ i11 = -1;
+
+ continue;
+ }
+ }
+
+ for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
+ parts->push_back(iter1->get());
+ }
+
+ return 1;
+}
+
+int TriangulatorPartition::ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts) {
+ List<TriangulatorPoly> outpolys;
+ List<TriangulatorPoly>::Element* iter;
+
+ if(!RemoveHoles(inpolys,&outpolys)) return 0;
+ for(iter=outpolys.front();iter;iter=iter->next()) {
+ if(!ConvexPartition_HM(&(iter->get()),parts)) return 0;
+ }
+ return 1;
+}
+
+//minimum-weight polygon triangulation by dynamic programming
+//O(n^3) time complexity
+//O(n^2) space complexity
+int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ long i,j,k,gap,n;
+ DPState **dpstates;
+ Vector2 p1,p2,p3,p4;
+ long bestvertex;
+ real_t weight,minweight,d1,d2;
+ Diagonal diagonal,newdiagonal;
+ List<Diagonal> diagonals;
+ TriangulatorPoly triangle;
+ int ret = 1;
+
+ n = poly->GetNumPoints();
+ dpstates = new DPState *[n];
+ for(i=1;i<n;i++) {
+ dpstates[i] = new DPState[i];
+ }
+
+ //init states and visibility
+ for(i=0;i<(n-1);i++) {
+ p1 = poly->GetPoint(i);
+ for(j=i+1;j<n;j++) {
+ dpstates[j][i].visible = true;
+ dpstates[j][i].weight = 0;
+ dpstates[j][i].bestvertex = -1;
+ if(j!=(i+1)) {
+ p2 = poly->GetPoint(j);
+
+ //visibility check
+ if(i==0) p3 = poly->GetPoint(n-1);
+ else p3 = poly->GetPoint(i-1);
+ if(i==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(i+1);
+ if(!InCone(p3,p1,p4,p2)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ if(j==0) p3 = poly->GetPoint(n-1);
+ else p3 = poly->GetPoint(j-1);
+ if(j==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(j+1);
+ if(!InCone(p3,p2,p4,p1)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ for(k=0;k<n;k++) {
+ p3 = poly->GetPoint(k);
+ if(k==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(k+1);
+ if(Intersects(p1,p2,p3,p4)) {
+ dpstates[j][i].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ dpstates[n-1][0].visible = true;
+ dpstates[n-1][0].weight = 0;
+ dpstates[n-1][0].bestvertex = -1;
+
+ for(gap = 2; gap<n; gap++) {
+ for(i=0; i<(n-gap); i++) {
+ j = i+gap;
+ if(!dpstates[j][i].visible) continue;
+ bestvertex = -1;
+ for(k=(i+1);k<j;k++) {
+ if(!dpstates[k][i].visible) continue;
+ if(!dpstates[j][k].visible) continue;
+
+ if(k<=(i+1)) d1=0;
+ else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k));
+ if(j<=(k+1)) d2=0;
+ else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j));
+
+ weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
+
+ if((bestvertex == -1)||(weight<minweight)) {
+ bestvertex = k;
+ minweight = weight;
+ }
+ }
+ if(bestvertex == -1) {
+ for(i=1;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+
+ return 0;
+ }
+
+ dpstates[j][i].bestvertex = bestvertex;
+ dpstates[j][i].weight = minweight;
+ }
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_back(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front()->get());
+ diagonals.pop_front();
+ bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
+ if(bestvertex == -1) {
+ ret = 0;
+ break;
+ }
+ triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2));
+ triangles->push_back(triangle);
+ if(bestvertex > (diagonal.index1+1)) {
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = bestvertex;
+ diagonals.push_back(newdiagonal);
+ }
+ if(diagonal.index2 > (bestvertex+1)) {
+ newdiagonal.index1 = bestvertex;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_back(newdiagonal);
+ }
+ }
+
+ for(i=1;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+
+ return ret;
+}
+
+void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) {
+ Diagonal newdiagonal;
+ List<Diagonal> *pairs;
+ long w2;
+
+ w2 = dpstates[a][b].weight;
+ if(w>w2) return;
+
+ pairs = &(dpstates[a][b].pairs);
+ newdiagonal.index1 = i;
+ newdiagonal.index2 = j;
+
+ if(w<w2) {
+ pairs->clear();
+ pairs->push_front(newdiagonal);
+ dpstates[a][b].weight = w;
+ } else {
+ if((!pairs->empty())&&(i <= pairs->front()->get().index1)) return;
+ while((!pairs->empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front();
+ pairs->push_front(newdiagonal);
+ }
+}
+
+void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ List<Diagonal> *pairs;
+ List<Diagonal>::Element *iter,*lastiter;
+ long top;
+ long w;
+
+ if(!dpstates[i][j].visible) return;
+ top = j;
+ w = dpstates[i][j].weight;
+ if(k-j > 1) {
+ if (!dpstates[j][k].visible) return;
+ w += dpstates[j][k].weight + 1;
+ }
+ if(j-i > 1) {
+ pairs = &(dpstates[i][j].pairs);
+ iter = NULL;
+ lastiter = NULL;
+ while(iter!=pairs->front()) {
+ if (!iter)
+ iter=pairs->back();
+ else
+ iter=iter->prev();
+
+ if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter;
+ else break;
+ }
+ if(lastiter == NULL) w++;
+ else {
+ if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++;
+ else top = lastiter->get().index1;
+ }
+ }
+ UpdateState(i,k,w,top,j,dpstates);
+}
+
+void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ List<Diagonal> *pairs;
+ List<Diagonal>::Element* iter,*lastiter;
+ long top;
+ long w;
+
+ if(!dpstates[j][k].visible) return;
+ top = j;
+ w = dpstates[j][k].weight;
+
+ if (j-i > 1) {
+ if (!dpstates[i][j].visible) return;
+ w += dpstates[i][j].weight + 1;
+ }
+ if (k-j > 1) {
+ pairs = &(dpstates[j][k].pairs);
+
+ iter = pairs->front();
+ if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) {
+ lastiter = iter;
+ while(iter!=NULL) {
+ if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) {
+ lastiter = iter;
+ iter=iter->next();
+ }
+ else break;
+ }
+ if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++;
+ else top = lastiter->get().index2;
+ } else w++;
+ }
+ UpdateState(i,k,w,j,top,dpstates);
+}
+
+int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
+ Vector2 p1,p2,p3,p4;
+ PartitionVertex *vertices;
+ DPState2 **dpstates;
+ long i,j,k,n,gap;
+ List<Diagonal> diagonals,diagonals2;
+ Diagonal diagonal,newdiagonal;
+ List<Diagonal> *pairs,*pairs2;
+ List<Diagonal>::Element* iter,*iter2;
+ int ret;
+ TriangulatorPoly newpoly;
+ List<long> indices;
+ List<long>::Element* iiter;
+ bool ijreal,jkreal;
+
+ n = poly->GetNumPoints();
+ vertices = new PartitionVertex[n];
+
+ dpstates = new DPState2 *[n];
+ for(i=0;i<n;i++) {
+ dpstates[i] = new DPState2[n];
+ }
+
+ //init vertex information
+ for(i=0;i<n;i++) {
+ vertices[i].p = poly->GetPoint(i);
+ vertices[i].isActive = true;
+ if(i==0) vertices[i].previous = &(vertices[n-1]);
+ else vertices[i].previous = &(vertices[i-1]);
+ if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]);
+ else vertices[i].next = &(vertices[i+1]);
+ }
+ for(i=1;i<n;i++) {
+ UpdateVertexReflexity(&(vertices[i]));
+ }
+
+ //init states and visibility
+ for(i=0;i<(n-1);i++) {
+ p1 = poly->GetPoint(i);
+ for(j=i+1;j<n;j++) {
+ dpstates[i][j].visible = true;
+ if(j==i+1) {
+ dpstates[i][j].weight = 0;
+ } else {
+ dpstates[i][j].weight = 2147483647;
+ }
+ if(j!=(i+1)) {
+ p2 = poly->GetPoint(j);
+
+ //visibility check
+ if(!InCone(&vertices[i],p2)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+ if(!InCone(&vertices[j],p1)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+
+ for(k=0;k<n;k++) {
+ p3 = poly->GetPoint(k);
+ if(k==(n-1)) p4 = poly->GetPoint(0);
+ else p4 = poly->GetPoint(k+1);
+ if(Intersects(p1,p2,p3,p4)) {
+ dpstates[i][j].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ for(i=0;i<(n-2);i++) {
+ j = i+2;
+ if(dpstates[i][j].visible) {
+ dpstates[i][j].weight = 0;
+ newdiagonal.index1 = i+1;
+ newdiagonal.index2 = i+1;
+ dpstates[i][j].pairs.push_back(newdiagonal);
+ }
+ }
+
+ dpstates[0][n-1].visible = true;
+ vertices[0].isConvex = false; //by convention
+
+ for(gap=3; gap<n; gap++) {
+ for(i=0;i<n-gap;i++) {
+ if(vertices[i].isConvex) continue;
+ k = i+gap;
+ if(dpstates[i][k].visible) {
+ if(!vertices[k].isConvex) {
+ for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates);
+ } else {
+ for(j=i+1;j<(k-1);j++) {
+ if(vertices[j].isConvex) continue;
+ TypeA(i,j,k,vertices,dpstates);
+ }
+ TypeA(i,k-1,k,vertices,dpstates);
+ }
+ }
+ }
+ for(k=gap;k<n;k++) {
+ if(vertices[k].isConvex) continue;
+ i = k-gap;
+ if((vertices[i].isConvex)&&(dpstates[i][k].visible)) {
+ TypeB(i,i+1,k,vertices,dpstates);
+ for(j=i+2;j<k;j++) {
+ if(vertices[j].isConvex) continue;
+ TypeB(i,j,k,vertices,dpstates);
+ }
+ }
+ }
+ }
+
+
+ //recover solution
+ ret = 1;
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_front(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front()->get());
+ diagonals.pop_front();
+ if((diagonal.index2 - diagonal.index1) <=1) continue;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if(pairs->empty()) {
+ ret = 0;
+ break;
+ }
+ if(!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+
+ j = iter->get().index2;
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ if((j - diagonal.index1)>1) {
+ if(iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[diagonal.index1][j].pairs);
+ while(1) {
+ if(pairs2->empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->back();
+
+ if(iter->get().index1 != iter2->get().index1) pairs2->pop_back();
+ else break;
+ }
+ if(ret == 0) break;
+ }
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ }
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ if((diagonal.index2 - j) > 1) {
+ if(iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[j][diagonal.index2].pairs);
+ while(1) {
+ if(pairs2->empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->front();
+ if(iter->get().index2 != iter2->get().index2) pairs2->pop_front();
+ else break;
+ }
+ if(ret == 0) break;
+ }
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ }
+ }
+ }
+
+ if(ret == 0) {
+ for(i=0;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+ delete [] vertices;
+
+ return ret;
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n-1;
+ diagonals.push_front(newdiagonal);
+ while(!diagonals.empty()) {
+ diagonal = (diagonals.front())->get();
+ diagonals.pop_front();
+ if((diagonal.index2 - diagonal.index1) <= 1) continue;
+
+ indices.clear();
+ diagonals2.clear();
+ indices.push_back(diagonal.index1);
+ indices.push_back(diagonal.index2);
+ diagonals2.push_front(diagonal);
+
+ while(!diagonals2.empty()) {
+ diagonal = (diagonals2.front()->get());
+ diagonals2.pop_front();
+ if((diagonal.index2 - diagonal.index1) <= 1) continue;
+ ijreal = true;
+ jkreal = true;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if(!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+ j = iter->get().index2;
+ if(iter->get().index1 != iter->get().index2) ijreal = false;
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ if(iter->get().index1 != iter->get().index2) jkreal = false;
+ }
+
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ if(ijreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ if(jkreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ indices.push_back(j);
+ }
+
+ indices.sort();
+ newpoly.Init((long)indices.size());
+ k=0;
+ for(iiter = indices.front();iiter;iiter=iiter->next()) {
+ newpoly[k] = vertices[iiter->get()].p;
+ k++;
+ }
+ parts->push_back(newpoly);
+ }
+
+ for(i=0;i<n;i++) {
+ delete [] dpstates[i];
+ }
+ delete [] dpstates;
+ delete [] vertices;
+
+ return ret;
+}
+
+//triangulates a set of polygons by first partitioning them into monotone polygons
+//O(n*log(n)) time complexity, O(n) space complexity
+//the algorithm used here is outlined in the book
+//"Computational Geometry: Algorithms and Applications"
+//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
+int TriangulatorPartition::MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys) {
+ List<TriangulatorPoly>::Element *iter;
+ MonotoneVertex *vertices;
+ long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices;
+ long polystartindex, polyendindex;
+ TriangulatorPoly *poly;
+ MonotoneVertex *v,*v2,*vprev,*vnext;
+ ScanLineEdge newedge;
+ bool error = false;
+
+ numvertices = 0;
+ for(iter = inpolys->front(); iter ; iter=iter->next()) {
+ numvertices += iter->get().GetNumPoints();
+ }
+
+ maxnumvertices = numvertices*3;
+ vertices = new MonotoneVertex[maxnumvertices];
+ newnumvertices = numvertices;
+
+ polystartindex = 0;
+ for(iter = inpolys->front(); iter ; iter=iter->next()) {
+ poly = &(iter->get());
+ polyendindex = polystartindex + poly->GetNumPoints()-1;
+ for(i=0;i<poly->GetNumPoints();i++) {
+ vertices[i+polystartindex].p = poly->GetPoint(i);
+ if(i==0) vertices[i+polystartindex].previous = polyendindex;
+ else vertices[i+polystartindex].previous = i+polystartindex-1;
+ if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex;
+ else vertices[i+polystartindex].next = i+polystartindex+1;
+ }
+ polystartindex = polyendindex+1;
+ }
+
+ //construct the priority queue
+ long *priority = new long [numvertices];
+ for(i=0;i<numvertices;i++) priority[i] = i;
+ SortArray<long,VertexSorter> sorter;
+ sorter.compare.vertices=vertices;
+ sorter.sort(priority,numvertices);
+
+ //determine vertex types
+ char *vertextypes = new char[maxnumvertices];
+ for(i=0;i<numvertices;i++) {
+ v = &(vertices[i]);
+ vprev = &(vertices[v->previous]);
+ vnext = &(vertices[v->next]);
+
+ if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) {
+ if(IsConvex(vnext->p,vprev->p,v->p)) {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START;
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT;
+ }
+ } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) {
+ if(IsConvex(vnext->p,vprev->p,v->p))
+ {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END;
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE;
+ }
+ } else {
+ vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR;
+ }
+ }
+
+ //helpers
+ long *helpers = new long[maxnumvertices];
+
+ //binary search tree that holds edges intersecting the scanline
+ //note that while set doesn't actually have to be implemented as a tree
+ //complexity requirements for operations are the same as for the balanced binary search tree
+ Set<ScanLineEdge> edgeTree;
+ //store iterators to the edge tree elements
+ //this makes deleting existing edges much faster
+ Set<ScanLineEdge>::Element **edgeTreeIterators,*edgeIter;
+ edgeTreeIterators = new Set<ScanLineEdge>::Element*[maxnumvertices];
+ //Pair<Set<ScanLineEdge>::Element*,bool> edgeTreeRet;
+ for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = NULL;
+
+ //for each vertex
+ for(i=0;i<numvertices;i++) {
+ vindex = priority[i];
+ v = &(vertices[vindex]);
+ vindex2 = vindex;
+ v2 = v;
+
+ //depending on the vertex type, do the appropriate action
+ //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications"
+ switch(vertextypes[vindex]) {
+ case TRIANGULATOR_VERTEXTYPE_START:
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v->p;
+ newedge.p2 = vertices[v->next].p;
+ newedge.index = vindex;
+ edgeTreeIterators[vindex] = edgeTree.insert(newedge);
+ helpers[vindex] = vindex;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_END:
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //Delete ei-1 from T
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_SPLIT:
+ //Search in T to find the edge e j directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //Insert the diagonal connecting vi to helper(ej) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex;
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex2;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_MERGE:
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ }
+ //Delete ei-1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ //Search in T to find the edge e j directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //if helper(ej) is a merge vertex
+ if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(e j) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex2;
+ break;
+
+ case TRIANGULATOR_VERTEXTYPE_REGULAR:
+ //if the interior of P lies to the right of vi
+ if(Below(v->p,vertices[v->previous].p)) {
+ //if helper(ei-1) is a merge vertex
+ if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(ei-1) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices-2;
+ v2 = &(vertices[vindex2]);
+ }
+ //Delete ei-1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ //Insert ei in T and set helper(ei) to vi.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex;
+ } else {
+ //Search in T to find the edge ej directly left of vi.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if(edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter=edgeIter->prev();
+ //if helper(ej) is a merge vertex
+ if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
+ //Insert the diagonal connecting vi to helper(e j) in D.
+ AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ //helper(e j)�vi
+ helpers[edgeIter->get().index] = vindex;
+ }
+ break;
+ }
+
+ if(error) break;
+ }
+
+ char *used = new char[newnumvertices];
+ memset(used,0,newnumvertices*sizeof(char));
+
+ if(!error) {
+ //return result
+ long size;
+ TriangulatorPoly mpoly;
+ for(i=0;i<newnumvertices;i++) {
+ if(used[i]) continue;
+ v = &(vertices[i]);
+ vnext = &(vertices[v->next]);
+ size = 1;
+ while(vnext!=v) {
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ mpoly.Init(size);
+ v = &(vertices[i]);
+ mpoly[0] = v->p;
+ vnext = &(vertices[v->next]);
+ size = 1;
+ used[i] = 1;
+ used[v->next] = 1;
+ while(vnext!=v) {
+ mpoly[size] = vnext->p;
+ used[vnext->next] = 1;
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ monotonePolys->push_back(mpoly);
+ }
+ }
+
+ //cleanup
+ delete [] vertices;
+ delete [] priority;
+ delete [] vertextypes;
+ delete [] edgeTreeIterators;
+ delete [] helpers;
+ delete [] used;
+
+ if(error) {
+ return 0;
+ } else {
+ return 1;
+ }
+}
+
+//adds a diagonal to the doubly-connected list of vertices
+void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers)
+{
+ long newindex1,newindex2;
+
+ newindex1 = *numvertices;
+ (*numvertices)++;
+ newindex2 = *numvertices;
+ (*numvertices)++;
+
+ vertices[newindex1].p = vertices[index1].p;
+ vertices[newindex2].p = vertices[index2].p;
+
+ vertices[newindex2].next = vertices[index2].next;
+ vertices[newindex1].next = vertices[index1].next;
+
+ vertices[vertices[index2].next].previous = newindex2;
+ vertices[vertices[index1].next].previous = newindex1;
+
+ vertices[index1].next = newindex2;
+ vertices[newindex2].previous = index1;
+
+ vertices[index2].next = newindex1;
+ vertices[newindex1].previous = index2;
+
+ //update all relevant structures
+ vertextypes[newindex1] = vertextypes[index1];
+ edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
+ helpers[newindex1] = helpers[index1];
+ if(edgeTreeIterators[newindex1] != NULL)
+ edgeTreeIterators[newindex1]->get().index = newindex1;
+ vertextypes[newindex2] = vertextypes[index2];
+ edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
+ helpers[newindex2] = helpers[index2];
+ if(edgeTreeIterators[newindex2] != NULL)
+ edgeTreeIterators[newindex2]->get().index = newindex2;
+}
+
+bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) {
+ if(p1.y < p2.y) return true;
+ else if(p1.y == p2.y) {
+ if(p1.x < p2.x) return true;
+ }
+ return false;
+}
+
+
+
+
+
+//sorts in the falling order of y values, if y is equal, x is used instead
+bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const {
+ if(vertices[index1].p.y > vertices[index2].p.y) return true;
+ else if(vertices[index1].p.y == vertices[index2].p.y) {
+ if(vertices[index1].p.x > vertices[index2].p.x) return true;
+ }
+ return false;
+}
+
+bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const {
+ real_t tmp;
+ tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
+ if(tmp>0) return 1;
+ else return 0;
+}
+
+bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const {
+ if(other.p1.y == other.p2.y) {
+ if(p1.y == p2.y) {
+ if(p1.y < other.p1.y) return true;
+ else return false;
+ }
+ if(IsConvex(p1,p2,other.p1)) return true;
+ else return false;
+ } else if(p1.y == p2.y) {
+ if(IsConvex(other.p1,other.p2,p1)) return false;
+ else return true;
+ } else if(p1.y < other.p1.y) {
+ if(IsConvex(other.p1,other.p2,p1)) return false;
+ else return true;
+ } else {
+ if(IsConvex(p1,p2,other.p1)) return true;
+ else return false;
+ }
+}
+
+//triangulates monotone polygon
+//O(n) time, O(n) space complexity
+int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles) {
+ long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex;
+ Vector2 *points;
+ long numpoints;
+ TriangulatorPoly triangle;
+
+ numpoints = inPoly->GetNumPoints();
+ points = inPoly->GetPoints();
+
+ //trivial calses
+ if(numpoints < 3) return 0;
+ if(numpoints == 3) {
+ triangles->push_back(*inPoly);
+ }
+
+ topindex = 0; bottomindex=0;
+ for(i=1;i<numpoints;i++) {
+ if(Below(points[i],points[bottomindex])) bottomindex = i;
+ if(Below(points[topindex],points[i])) topindex = i;
+ }
+
+ //check if the poly is really monotone
+ i = topindex;
+ while(i!=bottomindex) {
+ i2 = i+1; if(i2>=numpoints) i2 = 0;
+ if(!Below(points[i2],points[i])) return 0;
+ i = i2;
+ }
+ i = bottomindex;
+ while(i!=topindex) {
+ i2 = i+1; if(i2>=numpoints) i2 = 0;
+ if(!Below(points[i],points[i2])) return 0;
+ i = i2;
+ }
+
+ char *vertextypes = new char[numpoints];
+ long *priority = new long[numpoints];
+
+ //merge left and right vertex chains
+ priority[0] = topindex;
+ vertextypes[topindex] = 0;
+ leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0;
+ rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1;
+ for(i=1;i<(numpoints-1);i++) {
+ if(leftindex==bottomindex) {
+ priority[i] = rightindex;
+ rightindex--; if(rightindex<0) rightindex = numpoints-1;
+ vertextypes[priority[i]] = -1;
+ } else if(rightindex==bottomindex) {
+ priority[i] = leftindex;
+ leftindex++; if(leftindex>=numpoints) leftindex = 0;
+ vertextypes[priority[i]] = 1;
+ } else {
+ if(Below(points[leftindex],points[rightindex])) {
+ priority[i] = rightindex;
+ rightindex--; if(rightindex<0) rightindex = numpoints-1;
+ vertextypes[priority[i]] = -1;
+ } else {
+ priority[i] = leftindex;
+ leftindex++; if(leftindex>=numpoints) leftindex = 0;
+ vertextypes[priority[i]] = 1;
+ }
+ }
+ }
+ priority[i] = bottomindex;
+ vertextypes[bottomindex] = 0;
+
+ long *stack = new long[numpoints];
+ long stackptr = 0;
+
+ stack[0] = priority[0];
+ stack[1] = priority[1];
+ stackptr = 2;
+
+ //for each vertex from top to bottom trim as many triangles as possible
+ for(i=2;i<(numpoints-1);i++) {
+ vindex = priority[i];
+ if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) {
+ for(j=0;j<(stackptr-1);j++) {
+ if(vertextypes[vindex]==1) {
+ triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+ stack[0] = priority[i-1];
+ stack[1] = priority[i];
+ stackptr = 2;
+ } else {
+ stackptr--;
+ while(stackptr>0) {
+ if(vertextypes[vindex]==1) {
+ if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) {
+ triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ } else {
+ if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) {
+ triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ }
+ }
+ stackptr++;
+ stack[stackptr] = vindex;
+ stackptr++;
+ }
+ }
+ vindex = priority[i];
+ for(j=0;j<(stackptr-1);j++) {
+ if(vertextypes[stack[j+1]]==1) {
+ triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+
+ delete [] priority;
+ delete [] vertextypes;
+ delete [] stack;
+
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> monotone;
+ List<TriangulatorPoly>::Element* iter;
+
+ if(!MonotonePartition(inpolys,&monotone)) return 0;
+ for(iter = monotone.front(); iter;iter=iter->next()) {
+ if(!TriangulateMonotone(&(iter->get()),triangles)) return 0;
+ }
+ return 1;
+}
+
+int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
+ List<TriangulatorPoly> polys;
+ polys.push_back(*poly);
+
+ return Triangulate_MONO(&polys, triangles);
+}
diff --git a/thirdparty/misc/triangulator.h b/thirdparty/misc/triangulator.h
new file mode 100644
index 0000000000..b6dd7e8236
--- /dev/null
+++ b/thirdparty/misc/triangulator.h
@@ -0,0 +1,306 @@
+//Copyright (C) 2011 by Ivan Fratric
+//
+//Permission is hereby granted, free of charge, to any person obtaining a copy
+//of this software and associated documentation files (the "Software"), to deal
+//in the Software without restriction, including without limitation the rights
+//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+//copies of the Software, and to permit persons to whom the Software is
+//furnished to do so, subject to the following conditions:
+//
+//The above copyright notice and this permission notice shall be included in
+//all copies or substantial portions of the Software.
+//
+//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+//THE SOFTWARE.
+
+#ifndef TRIANGULATOR_H
+#define TRIANGULATOR_H
+
+#include "math_2d.h"
+#include "list.h"
+#include "set.h"
+//2D point structure
+
+
+#define TRIANGULATOR_CCW 1
+#define TRIANGULATOR_CW -1
+//Polygon implemented as an array of points with a 'hole' flag
+class TriangulatorPoly {
+protected:
+
+
+
+ Vector2 *points;
+ long numpoints;
+ bool hole;
+
+public:
+
+ //constructors/destructors
+ TriangulatorPoly();
+ ~TriangulatorPoly();
+
+ TriangulatorPoly(const TriangulatorPoly &src);
+ TriangulatorPoly& operator=(const TriangulatorPoly &src);
+
+ //getters and setters
+ long GetNumPoints() {
+ return numpoints;
+ }
+
+ bool IsHole() {
+ return hole;
+ }
+
+ void SetHole(bool hole) {
+ this->hole = hole;
+ }
+
+ Vector2 &GetPoint(long i) {
+ return points[i];
+ }
+
+ Vector2 *GetPoints() {
+ return points;
+ }
+
+ Vector2& operator[] (int i) {
+ return points[i];
+ }
+
+ //clears the polygon points
+ void Clear();
+
+ //inits the polygon with numpoints vertices
+ void Init(long numpoints);
+
+ //creates a triangle with points p1,p2,p3
+ void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3);
+
+ //inverts the orfer of vertices
+ void Invert();
+
+ //returns the orientation of the polygon
+ //possible values:
+ // Triangulator_CCW : polygon vertices are in counter-clockwise order
+ // Triangulator_CW : polygon vertices are in clockwise order
+ // 0 : the polygon has no (measurable) area
+ int GetOrientation();
+
+ //sets the polygon orientation
+ //orientation can be
+ // Triangulator_CCW : sets vertices in counter-clockwise order
+ // Triangulator_CW : sets vertices in clockwise order
+ void SetOrientation(int orientation);
+};
+
+class TriangulatorPartition {
+protected:
+ struct PartitionVertex {
+ bool isActive;
+ bool isConvex;
+ bool isEar;
+
+ Vector2 p;
+ real_t angle;
+ PartitionVertex *previous;
+ PartitionVertex *next;
+ };
+
+ struct MonotoneVertex {
+ Vector2 p;
+ long previous;
+ long next;
+ };
+
+ struct VertexSorter{
+ mutable MonotoneVertex *vertices;
+ bool operator() (long index1, long index2) const;
+ };
+
+ struct Diagonal {
+ long index1;
+ long index2;
+ };
+
+ //dynamic programming state for minimum-weight triangulation
+ struct DPState {
+ bool visible;
+ real_t weight;
+ long bestvertex;
+ };
+
+ //dynamic programming state for convex partitioning
+ struct DPState2 {
+ bool visible;
+ long weight;
+ List<Diagonal> pairs;
+ };
+
+ //edge that intersects the scanline
+ struct ScanLineEdge {
+ mutable long index;
+ Vector2 p1;
+ Vector2 p2;
+
+ //determines if the edge is to the left of another edge
+ bool operator< (const ScanLineEdge & other) const;
+
+ bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const;
+ };
+
+ //standard helper functions
+ bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3);
+ bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3);
+ bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p);
+
+ bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p);
+ bool InCone(PartitionVertex *v, Vector2 &p);
+
+ int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22);
+
+ Vector2 Normalize(const Vector2 &p);
+ real_t Distance(const Vector2 &p1, const Vector2 &p2);
+
+ //helper functions for Triangulate_EC
+ void UpdateVertexReflexity(PartitionVertex *v);
+ void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
+
+ //helper functions for ConvexPartition_OPT
+ void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
+ void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+ void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+
+ //helper functions for MonotonePartition
+ bool Below(Vector2 &p1, Vector2 &p2);
+ void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers);
+
+ //triangulates a monotone polygon, used in Triangulate_MONO
+ int TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles);
+
+public:
+
+ //simple heuristic procedure for removing holes from a list of polygons
+ //works by creating a diagonal from the rightmost hole vertex to some visible vertex
+ //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons that can contain holes
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // outpolys : a list of polygons without holes
+ //returns 1 on success, 0 on failure
+ int RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys);
+
+ //triangulates a polygon by ear clipping
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a list of polygons that may contain holes by ear clipping algorithm
+ //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon
+ //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
+
+ //creates an optimal polygon triangulation in terms of minimal edge length
+ //time complexity: O(n^3), n is the number of vertices
+ //space complexity: O(n^2)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a polygons by firstly partitioning it into monotone polygons
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be triangulated
+ // vertices have to be in counter-clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
+
+ //triangulates a list of polygons by firstly partitioning them into monotone polygons
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // triangles : a list of triangles (result)
+ //returns 1 on success, 0 on failure
+ int Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
+
+ //creates a monotone partition of a list of polygons that can contain holes
+ //time complexity: O(n*log(n)), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : a list of polygons to be triangulated (can contain holes)
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // monotonePolys : a list of monotone polygons (result)
+ //returns 1 on success, 0 on failure
+ int MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys);
+
+ //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm
+ //the algorithm gives at most four times the number of parts as the optimal algorithm
+ //however, in practice it works much better than that and often gives optimal partition
+ //uses triangulation obtained by ear clipping as intermediate result
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // poly : an input polygon to be partitioned
+ // vertices have to be in counter-clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
+
+ //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm
+ //the algorithm gives at most four times the number of parts as the optimal algorithm
+ //however, in practice it works much better than that and often gives optimal partition
+ //uses triangulation obtained by ear clipping as intermediate result
+ //time complexity O(n^2), n is the number of vertices
+ //space complexity: O(n)
+ //params:
+ // inpolys : an input list of polygons to be partitioned
+ // vertices of all non-hole polys have to be in counter-clockwise order
+ // vertices of all hole polys have to be in clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts);
+
+ //optimal convex partitioning (in terms of number of resulting convex polygons)
+ //using the Keil-Snoeyink algorithm
+ //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998
+ //time complexity O(n^3), n is the number of vertices
+ //space complexity: O(n^3)
+ // poly : an input polygon to be partitioned
+ // vertices have to be in counter-clockwise order
+ // parts : resulting list of convex polygons
+ //returns 1 on success, 0 on failure
+ int ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
+};
+
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 04:17:09 +0000