Pull to refresh

Comments 65

Ещё в процессе разжатия, видимо.
Кот, да не тот.


Кстати спасибо за интересный метод. У меня изображения были сильно меньше, но большим количеством. Приходилось использовать внешнюю flash — на контроллер оно и так и так не влезло бы, а с 1Мб флешкой смысла сжимать и не было.
После публикации, читается как «с котом»…
Мда, что-то не убедительно без исходных файлов картинок.
Для работы с 8 кб RAM можно на раз найти в инете пачку алгоритмов: LZSS, S-LZW, FastLZ…

Для малопотребляющего устройства наверно имеет значение скорость работы, так что не хватает еще сравнительной оценки энергопотребления.
lzss требует доступ к последнему расжатому блоку (2KB), который используется в качестве словаря. А тут видеобуфера нет.
… и 8 килобайтов на все. Вообще на все, не только на вывод картинки.
FastLZ вообще не требует памяти на декомпрессию.
Не существует словарных алгоритмов сжатия, не требующих «вообще» памяти на декомпрессию. Словарь, увы, необходимо где-то хранить.

github.com/ariya/FastLZ/blob/master/6unpack.c — посмотрите сами реализацию.

И не забывайте, пожалуйста, главное — необходимость потоковой распаковки.
Это не та ссылка.

Алгоритм
/*
  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)
#include "..\app.h"
/*
 * 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)
{
   flzuint8 *ip = (flzuint8 *)input;
   const flzuint8 *ip_bound = ip + length - 2;
   const flzuint8 *ip_limit = ip + length - 12;
   flzuint8 *op = (flzuint8 *)output;


   flzuint8 **htab;
   flzuint8 **hslot;
   flzuint32 hval;

   flzuint32 copy;


   htab = umm_malloc(HASH_SIZE*sizeof(flzuint8 *));
   if (htab == NULL) return 0;

   /* 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
          {
			      umm_free(htab);
                  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 */
      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

   umm_free(htab);
   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) */



Я не вижу в декомпрессоре выделения памяти.
Неважно выделяется память, или указатель на нее передается снаружи. Важно, что она должна быть. У нас физически нет места под распакованные данные.
А что происходит с распакованными данными? Они сразу отправляются на вывод? Если да — в каком порядке и формате?
Распаковка происходит в процессе вывода на экран, точнее заполнения сдвигового регистра, управляющего подачей напряжения на затворы транзисторов матрицы дисплея. Формат управляющей команды зависит от типа экрана.
Убедили. Реализации очень близкие. Разница в том, что вместо хранения ссылки и кода операции мы сразу распаковываем ее результат в RAM. Аргументация — удобство каскадирования с RLE и снижение числа обращений к флэшу. В остальном то же самое, код короче.
В качестве словаря используется (как и в LZSS) разжатый выходной поток:
...
flzuint8 *op = (flzuint8 *)output;
...
do {
  const flzuint8 *ref = op;
  //тут шаманство с ref
  ...
  //Ну и под конец при определенных условиях используем словарь
  for (; len; --len) *op++ = *ref++;
...
}


для алгоритма fastlz1 размер окна, как я понял, 8191 байт.
Да-да… Разжатый выходной поток означает необходимость его хранения.
Спасибо.
Я вчера к вечеру утратил ясность мышления.
Ну вы хоть, прежде чем алгоритмы с потолка предлагать, исходники-то читайте.
Здесь тоже нужно где-то хранить разжатые данные:
ucl_nrv2b_decompress_*(...)
        {
            const ucl_bytep m_pos;
            m_pos = dst + olen - m_off;
            dst[olen++] = *m_pos++;
            do dst[olen++] = *m_pos++; while (--m_len > 0);
        }
Про S-LZW вот, что нашел:
An implementation with a 512 entry dictionary requires
2618 bytes (plus four bytes for each additional entry)
of RAM and 1262 bytes of ROM

Т.е. все три алгоритма, предложенных вами, жрут непомерно много памяти для данного устройства. Заносите следующую тройку.
Жалко кота а не шакала сжимали… Ну вы поняли)
Нечто похожее можно было наблюдать для проекта «Казаки». Можно почитать ТУТ.
Были некоторые проблемы и в графическом департаменте. Огромные объемы двумерной графики, которыми приходилось оперировать, привели нас к созданию собственного формата: каждый кадр паковался отдельно, используя алгоритм LZ с общим словарем. За счет этого достигалась хорошая степень сжатия, а доступ к каждому кадру не требовал распаковки предыдущих.
Nordic NRF51822 (Cortex M0 + Bluetooth LE). Купить можно на Диджике, на Маузере, у нас тоже можно в форме платформ для разработки с электронной бумагой и радиопротоколами (но реклама вроде запрещена, поэтому без подробностей, чтобы не забанили, тем более, что цель поста другая).
Спасибо за пост!

Может быть кому-нибудь поможет и мой опыт.

Когда-то на позапрошлой работе я писал GIF под UEFI.
Так вот, в GIF'е картинку можно порезать на слои, + есть «прозрачный» цвет.
Я сжимал так: нарезал на слои один цвет + прозрачный цвет и все сжимал Лемпелем-Зивом-Велчем.

То есть если у меня N цветов, я разрезал на N слоев, в каждом из которых по 2 цвета. При цветах не более 14-18 (большинство картинок били именно в этой гамме) сжималось на ура!

Вообще GIF забавный формат… Есть масса способов упаковать картинку…
Котов давайте! Тоже хочется посжимать.
Какой классный кот. Что за порода?
У меня такой был беспородный :)
Из породистых имхо на сибиряка похож
а нельзя было прицепить какой-нибудь EEPROM через SPI?
Можно. Но у нас миллионная партия — считаем каждый цент.
ого. интересно было бы узнать подробнее про проект. если только не секретная военка…
Не секретная военка. Ценники для супермаркетов.
Как раз думал об этом, когда читал о том что нужно отображать картинки с сервера.
для наших или зарубежных? мне кажется, в наших такую игрушку быстро сопрут)))
Сопрут, так сопрут — она копеечная и как ее использовать мимо основного назначения — неочевидно.
Скажите пожалуйста, а ПО стека не влияет на производительность алгоритмов, не свойственных предназначеню чипа?
Влияет. Пришлось сделать маленькую RTOS, чтобы честно делить время между задачами… Об этом в одной из следующих серий.
(Вывод данных на экран в отсутствие видеобуфера и в присутствие крайней критичности к задержкам, оказался существенно более сильно лимитирующей задачей. Зато сжимая данные мы экономим на чтении и, особенно, записи в медленный флэш).
Буду ждать продолжение! Как раз стою перед выбором ртос именно для нордика, а заодно прикидываю справится ли ртос при работе совместно со стеком.
Справится. Если у Вас нет экстремистских запросов по памяти и энергопотреблению, берите RTX, для работы со стеком ее достаточно. В нашем случае они были (мы работаем с собственным high speed протоколом), но, возможно, мы переоценили их жесткость.
Ваш ответ перевесил чашу весов из rtx и frertos в пользу первой :)
Хитро! Быстро окупиться :)
Пока идешь дойдешь до кассы, ценник уже обновился.
Фотография может немножко снизить подобные риски.
Этот котик довольно легко упаковался в 329000 бит, и с большим трудом — в 306000. Выигрыш по сравнению с сырыми данными — от 3 до 3.2 раза, До 7 раз очень далеко :(
Ну, я ж не утверждаю, что в 7 раз сжимается любой произвольно взятый кот… Более того, в 7 раз сжимается не кот, а типовой ценник типового магазина, причем это — среднее значение по целевой выборке. Некоторые сжимаются в 20 раз, некоторые на 20%. Увы.
Точно бит? А то исходная картинка одну дискету весит.
Да, 41 килобайт. Исходная картинка — 4-цветная, по 2 бита на пиксель занимает 120 килобайт.
несмотря на то, что из теории известно, что LZ77 — это обобщение RLE

Поясните, пожалуйста. Всё же эти методы очень сильно отличаются.
Да не особо. RLE — это оконное сжатие с размером окна, равным единице и кодированием количества повторений вхождения, вместо длины совпадения (поскольку длина совпадения либо 0, либо 1).
Мы, наверное, по-разному понимаем похожесть. В RLE нет словаря, а это важная отличительная особенность алгоритмов LZ*. И обратно, в LZ77 нет счётчика повторений.

Непонятна роль единичного окна, если всё равно мы кодируем длины цепочек, выходящих за его пределы. А когда мы заменяем длину совпадения количеством повторений, мы выбрасываем последний оставшийся элемент LZ77.

Впрочем, это не так уже и важно всё. Просто глаз за фразу зацепился.
Я тоже так думал еще со студенческих времен. А теперь попробуйте посмотреть по-другому. Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности. RLE копирует последовательность из одного символа много раз, LZ77 — последовательность многих символов один раз. Можно даже написать общий код, так, чтобы выбор алгоритма свелся к заданию параметров.
Оба метода восстанавливают данные путем копирования ранее встретившейся последовательности.

А, ну если так классифицировать, то согласен.
Было бы супер припилить к u8glib.
Ткнулся в код, а там…
return (size_t)-1;

Вы серьёзно?
Что случилось, где пожар?
Так, пожалуй, смотрелось бы лучше:
return ~(size_t)0;
Да, можно и так. Или вообще сделать константу отдельную…
Но это не особо важно — работает, значит, нормально.

Я другое хотел спросить: где прочитать про scanback? Что-то не могу найти описания алгоритма, а из кода вообще ничего не понял. Где тут преобразование происходит?
	*repeating_value = SB_Fetch(sb_handler);
	handler->mDecodedPortion = *repeating_value & ~0x80;
	handler->mMode = *repeating_value & 0x80;
	*repeating_value = SB_Fetch(sb_handler);
	handler->mPtr = 1;
	return *repeating_value;
}
Могу выслать архив с исходниками. Мы пока не придумали, как вычленить из проприетарного гита конкретно этот модуль так, чтобы не менять систему сборки всех зависимых от него проектов. Если останутся вопросы — прокомментирую. На выходе появится статья в журнал.
По названию статьи вспомнился сериал «Альф», где одноимённый главный герой рассказывал рецепт котиного сока.
«Берёшь кота и соковыжималку...», дальше на него махали руками и окончание рецепта неизвестно.
P.S. В сериале ни один кот не пострадал.
Код scanback, наконец, полностью в публичном доступе. Правда, пока без примеров.
Only those users with full accounts are able to leave comments. Log in, please.