Як один патент мало не вбив GIF, і чому ми досі живемо з наслідками

Маленька драма про великі гроші, яку ніколи не чули

Якщо ви народились після 90х , то для тебе GIF це просто формат картинок. Анімовані меми у твіттері, реакції в телеграмі, оце все.

Але є одна деталь, яку дуже рідко розповідають: GIF колись був у центрі найгучнішого патентного скандалу в історії інтернету. Настільки гучного, що в індустрії змінилося ставлення до патентів на алгоритми, з’явився нові формати, PNG як реакція на це, і десятки тисяч розробників по всьому світу одного дня прокинулися з усвідомленням, що вони, виявляється, порушують чужі права інтелектуальної власності. Вже як сім років.

Розкажу що там було, бо історія досить цікава, єстественно з кодом.

Спочатку почнемо про CompuServe

Коли я кажу “CompuServe” людям молодшим за 35, у них зазвичай десь такий погляд:

Але це один з прабатьків інтернету в тому вигляді, в якому ми його зараз знаємо.

CompuServe заснували ще в 1969 році в Огайо як підрозділ страхової компанії, що обслуговував їхні мейнфрейми. Тут класична історія: машинний час дорогий, мейнфрейми вночі простоюють, давайте продавати години комусь іншому. У 1979 вони пішли далі і запустили сервіс. Звичайна людина зі свого дому могла подзвонити на їх модем і потрапити в онлайн.

Це був не інтернет. Це була внутрішня мережа умовно. Закрита екосистема: форуми, чати, пошта, новини, файлові архіви, енциклопедії. Все на їхніх серверах, і доступне тільки підписникам, які платили погодинно. У 80-х і на початку 90-х це був один з основних способів для простих людей “вийти в онлайн”.

І ось у 1987 році інженер CompuServe на ім’я Стів Вілхайт стикнувся з типовою проблемою свого часу. Користувачі сиділи на Apple II, Commodore 64, IBM PC, Atari ST, Amiga, всі з різними графічними системами. Треба був універсальний формат картинок, який би стискався достатньо щоб не страждати завантажуючи його через 1200-бодний модем (150 байт/с).

Так народився GIF. Graphics Interchange Format.

Стиснення в ньому було реалізовано через алгоритм LZW, про який ми зараз поговоримо детальніше.

До речі, Вілхайт який у 2013 році, отримуючи Webby Award, спеціально вийшов на сцену з написом “It’s pronounced JIF”. Він наполягав що його дітище читається “джиф”.

Що таке LZW

Лемпель і Зів придумали в 1978 році базову ідею (LZ78), а Террі Велч у 1984 опублікував покращену версію в журналі IEEE Computer. Стаття називалась “A Technique for High-Performance Data Compression” і виглядала як звичайна академічна публікація.

Ідея алгоритму цікава. Ви стискаєте дані, замінюючи послідовності, які повторюються, на короткі коди зі словника. Геніальність у тому, що словник будується “на льоту” з самих даних, і декодеру не треба передавати його окремо. Декодер відновлює той самий словник синхронно, дивлячись на ту саму послідовність кодів.

Ось як виглядає енкодер на TypeScript:

function lzwEncode(input: string): number[] {
  // Словник: пара "рядок -> код".
  // На старті заповнюємо його всіма одиничними символами:
  // "A" -> 65, "B" -> 66, і так далі до 255.
  // Це означає: будь-який окремий символ ми вже вміємо стискати.
  const dictionary = new Map<string, number>();
  for (let i = 0; i < 256; i++) {
    dictionary.set(String.fromCharCode(i), i);
  }

  let nextCode = 256;        // наступний вільний номер для нових записів
  let current = '';          // те, що зараз "збираємо" перед виводом
  const output: number[] = [];

  // Ідемо по вхідному тексту посимвольно.
  // Намагаємося знайти у словнику ЯКОМОГА ДОВШУ послідовність,
  // яка співпадає з тим, що зараз читаємо.
  for (const char of input) {
    const combined = current + char;  // що буде, якщо додамо ще один символ?

    if (dictionary.has(combined)) {
      // Така довша послідовність вже відома словнику.
      // Не поспішаємо нічого виводити може, отримаємо ще довшу.
      current = combined;
    } else {
      // Такої довшої послідовності словник ще не знає.
      // Значить, current це найдовше, що ми могли витиснути.

      // Виводимо код того, що зібрали в current.
      output.push(dictionary.get(current)!);

      // Запам'ятовуємо нову послідовність на майбутнє.
      // Якщо вона трапиться знову стиснемо одним числом.
      dictionary.set(combined, nextCode++);

      // Починаємо збирати заново, з поточного символа.
      current = char;
    }
  }

  // Не забуваємо вивести те, що залишилось у буфері в кінці.
  if (current !== '') {
    output.push(dictionary.get(current)!);
  }

  return output;
}

Декодер виглядає так:

function lzwDecode(codes: number[]): string {
  // Декодер починає з ТОГО САМОГО стартового словника, що й енкодер.
  // Тільки тут навпаки: "код -> рядок", бо ми отримуємо коди
  // і хочемо повернути назад текст.
  const dictionary = new Map<number, string>();
  for (let i = 0; i < 256; i++) {
    dictionary.set(i, String.fromCharCode(i));
  }

  let nextCode = 256;

  // Найкрасивіша частина LZW: словник нікуди не передається!
  // Декодер будує його сам, дивлячись на коди в тому ж порядку,
  // що й енкодер. Якщо обидва дотримуються однакових правил, то
  // словники в обох сторонах вийдуть ідентичні.

  // Перший код завжди простий це один з базових 256 символів.
  let previous = dictionary.get(codes[0])!;
  let result = previous;

  for (let i = 1; i < codes.length; i++) {
    const code = codes[i];
    let entry: string;

    if (dictionary.has(code)) {
      // Звичайна ситуація: код вже є у словнику, просто беремо рядок.
      entry = dictionary.get(code)!;
    } else if (code === nextCode) {
      // Іноді енкодер використовує код, який
      // декодер тільки збирається додати в словник (декодер
      // завжди трошки відстає). Але ми можемо здогадатися, що
      // там було, попередній рядок + його перший символ.
      // Це працює для повторюваних послідовностей типу "ababab".
      entry = previous + previous[0];
    } else {
      throw new Error(`Невалідний код: ${code}`);
    }

    // Додаємо розкодований шматок до результату.
    result += entry;

    // А тут сінкаємо словник з енкодером:
    // додаємо такий самий запис, який енкодер додавав на цьому ж кроці.
    dictionary.set(nextCode++, previous + entry[0]);
    previous = entry;
  }

  return result;
}

Розглянемо на прикладі. Беремо вхід умовно ABABABA:

Крок | current | char | combined | дія                          | вихід | словник
-----+---------+------+----------+------------------------------+-------+----------
1    | ""      | A    | "A"      | є → current = "A"            |       |
2    | "A"     | B    | "AB"     | немає → вивід код("A")       | 65    | "AB"=256
3    | "B"     | A    | "BA"     | немає → вивід код("B")       | 66    | "BA"=257
4    | "A"     | B    | "AB"     | є → current = "AB"           |       |
5    | "AB"    | A    | "ABA"    | немає → вивід код("AB")      | 256   | "ABA"=258
6    | "A"     | кінець          | вивід код("A")               | 65    |

На виході бачимо 4 коди замість 7 символів. На реальних даних з повторним стисненням може бути ще краще.

Алгоритм був швидкий, простий у реалізації, давав пристойне стиснення. Не дивно, що його почали юзати скрізь. GIF, TIFF, утиліта compress в Unix, модеми V.42bis, PostScript Level 2.

Патент, який ніхто не помічав

Велч у статті 1984 року не згадав ні слова про те, що подав патентну заявку. Інженери, які читали статтю (включно з Вілхайтом з CompuServe), вирішили що це звичайна академічна публікація. Алгоритм пішов у народ.

У 1985 Велчу видали патент US 4,558,302 “High speed data compression and decompression apparatus and method”. Він тоді працював у Sperry Corporation, яка через рік злилася з Burroughs і стала Unisys.

Таке ще називають патент-підводний човен.

Логіка проста: ти подаєш заявку, потім роками затягуєш її проходження через патентний офіс, або просто тихо сидиш зі свіжовиданим патентом і чекаєш. Чекаєш поки твій алгоритм не пошириться по індустрії, не побудують реальні продукти, доки відмова від нього не стане болючою. І тільки тоді вспливаєш з вимогою платити.

Sperry/Unisys сиділа з патентом тихо майже десять років. Вони ліцензували його великим виробникам модемів. Поки не настав 1993 рік.

До 1993 року три речі склалися разом. По-перше, Web почав рости. По-друге, GIF став основним форматом картинок. По-третє, Unisys нарешті провела внутрішній аудит і зрозуміла масштаб того, що в неї лежить у портфелі.

У грудні 1994 Unisys і CompuServe оголосили спільну заяву. CompuServe ліцензує LZW в Unisys і тепер вимагатиме ліцензійні відрахування від усіх розробників, що працюють з GIF.

Народження PNG

У 1995 році група розробників на чолі з Томасом Боутеллом за кілька місяців створила PNG. Portable Network Graphics. Формат без патентних обмежень, з кращим стисненням (через deflate/zlib), повноцінною прозорістю, gamma-корекцією. У 1996 PNG став стандартом W3C.

Абревіатура жартома розшифровувалась як “PNG’s Not GIF”.

Burn All GIFs Day

Комьюніті 5 листопада 1999 року організували акцію “Burn All GIFs Day”. Закликали видаляти GIF з сайтів і замінювати на PNG. Більшість зробила це символічно, але культурний слід акція залишила надовго.

Сторінка burnallgifs.org існувала ще багато років після того як патент закінчився, нагадуючи про цю історію.

Патент у США закінчився 20 червня 2003. Європейський, японський, канадський протягом 2004. Unisys встигла зібрати ліцензійних відрахувань на десятки мільйонів доларів за цей час.

PNG зайняв нішу картинок і досі там домінує.

GIF втратив технічну перевагу, більшість сучасних “гіфок” у твіттері, реддіті, телеграмі це насправді MP4 або WebP під капотом. Бо справжній GIF страшенно неефективний.

Слово “GIF” стало назвою для короткої анімації.

Ось така історія :)