Případ GIF

Obsah

1. Úvodní informace o grafickém formátu GIF
2. Vznik, vývoj a rozšíření formátu GIF
3. „Patent na GIFy“?
4. Stručný přehled celé kauzy
5. Better, smaller, more extensible, and FREE
6. Kauza se vytrácí do ztracena
7. Důsledky a poučení
8. Literatura a odkazy na Internetu
9. O čem si povíme příště?

1. Úvodní informace o grafickém formátu GIF

V tomto článku si uvedeme některé zajímavé informace týkající se zejména velmi sporných licenčních podmínek k populárnímu souborovému formátu GIF, který je určen pro ukládání a přenos rastrových obrázků s barevnou paletou. V následujícím pokračování se zaměřím na popis vlastností GIFu a také uvedu na pravou míru jeden mýtus tradovaný už skoro dvacet let. GIF, resp. celé sousloví Graphics Interchange Format, je obchodní značka firem CompuServe a H&R Block Company, název je však možné volně používat (například při označování typů souborů nebo v názvu produktu). Tento grafický formát existuje ve dvou variantách pojmenovaných podle roku svého vzniku. Jedná se o variantu 87a (představenou 15.6.1987) a variantu 89a z roku 1989, která však byla veřejnosti prezentována až v roce 1990; podle některých zdrojů to bylo prvního srpna, já však mám oficiální dokument s datem 31.7.1990. Grafický formát GIF byl a dosud je velmi populární, protože mu jeho autoři dali do vínku několik užitečných vlastností, zejména tyto:

1. Jedná se o velmi dobře dokumentovaný formát, s poměrně účinnou kompresí, který je jednoduchý jak pro čtení, tak i pro zápis. Dokumentace je dobře napsaná a čtivá; pro verzi 87a má cca 30kB, pro verzi 89a cca 80kB čistého textu s ASCII tabulkami a diagramy. Vlastní formát neobsahuje žádné zbytečnosti a nelogičnosti (na rozdíl od např. BMP s několika hlavičkami, nadměrně velkými, popř. zbytečnými položkami, neúsporným zápisem barvové palety atd.).
2. Použití komprimačního algoritmu LZW zaručilo rychlou a účinnou kompresi (a později také tahanice okolo licenčních podmínek). V osmdesátých letech šlo o vyspělou technologii, další grafické formáty většinou používaly méně účinnou komprimaci pomocí různých modifikací algoritmu RLE.
3. Formát GIF byl současně multiplatformní, jeho použití není vázáno na žádný operační systém, procesor ani grafickou kartu. Dokonce existují prohlížeče GIFů i na tak paměťově a výkonově „slabých“ strojích, jakými jsou osmibitová Atari a Commodore C64. Snadná implementovatelnost je zaručena i tím, že hashovací tabulka může obsahovat maximálně 2¹² položek (více technických informací se dozvíte v následujícím pokračování).
4. Podpora více rámců, ze kterých je celý obraz složen, zajišťuje větší kompresní poměr (ovšem pokud je správně vytvořen zapisovací program), může zvýšit barevnou hloubku celého obrazu, slouží k tvorbě animací, sekvencí snímků apod. Jedná se o jednu z největších zbraní GIFu, která ke škodě nás všech nebyla přenesena do formátu PNG, který se měl stát následovníkem GIFu.
5. Většina ostatních grafických formátů omezuje volbu maximálního počtu položek v barvové paletě (a tím i celkový počet barev v obrázku). U GIFu může mít každý rámec svou lokální barvovou paletu s libovolným počtem barev v rozsahu 2–256. Počet bitů na pixel je také volitelný a může dosahovat libovolné hodnoty 1–8.
6. Při přenosu rastrových obrázků po pomalých přenosových linkách (modemy atd.) se uplatnila možnost prokládání řádků v jednotlivých rámcích. Prokládání funguje tak, že se nejdříve přenese každý osmý řádek, posléze každý čtvrtý řádek (kromě těch přenesených), a tak dále do posledního kroku, ve kterém jsou přeneseny všechny ostatní, tj. sudé řádky. Uživatel si může představu o celém obrázku utvořit již při přenesení cca jedné osminy dat a přenos popř. přerušit. Podobnou funkcionalitu nabízí i grafický formát JPEG a PNG.
7. GIF také umožnil, aby jedna barva z barvové palety byla v každém rámci uvedena jako barva průhledná. Díky tomu bylo možné vytvářet obrázky se zdánlivě neobdélníkovými okraji. Další grafické formáty (například PNG a TGA) rozšířily původně jednobitovou průhlednost (každý pixel může být buď zcela průhledný nebo zcela neprůhledný) do plnohodnotného alfa kanálu s bitovou šířkou 8 či dokonce 12 a 16 bitů.

2. Vznik, vývoj a rozšíření formátu GIF

Již v předchozím textu jsme si pověděli, že grafický formát GIF navrhla v roce 1987 firma CompuServe pro přednostní využití ve své komunitní síti. Vzhledem k tomu, že se jednalo o počítačovou síť, do které se uživatelé většinou připojovali pomocí relativně pomalých modemů, byl při návrhu GIF kladen důraz na co největší úsporu přenášených dat. Současně byl však formát GIF navržen velmi šťastným způsobem, o čemž svědčí i fakt, že je dodnes, tj. cca 20 let po svém vzniku, stále prakticky beze změny úspěšně používán, i když (jak si řekneme dále) dosud nejsou využity všechny jeho vlastnosti.

V rozmezí let 1987 až 1994 došlo k velkému rozšíření grafického formátu GIF jak mezi technicky zaměřenou počítačovou komunitou, tak i mezi běžnými uživateli počítačů a Internetu. GIF se díky svým vlastnostem stal jedním z cca čtyř grafických formátů, které bylo možné použít při publikování webových stránek. Současně se jednalo i o formát nenahraditelný; k tomuto tvrzení nám postačí porovnání se zbylými třemi v té době používanými formáty: černobílý XBM (historicky první grafický formát na Webu, ale dnes zcela zastaralý a například v IE 7 prý už nepodporovaný), formát BMP s velmi mizerným komprimačním algoritmem (mnoho aplikací pracuje dokonce pouze s nekomprimovaným BMP) a ztrátový formát JPEG, který je sice stále s úspěchem používán, ale pro zcela jiné účely než GIF.

Tvůrci formátu GIF použili pro komprimaci grafických údajů algoritmus LZW, což je modifikace algoritmů LZ77 a LZ78 (viz literatura). Kromě GIFu se tento algoritmus využívá například v unixové utilitě „compress“, volitelně v grafickém formátu TIFF a mimo jiné také v PostScriptu pro ukládání rastrových dat. Algoritmus LZW byl již v době návrhu GIFu patentován, podle dostupných informací však firma CompuServe o tomto faktu nevěděla (v opačném případě by pravděpodobně použila jiný algoritmus, například nepatentovaný LZ77).

3. „Patent na GIFy“?

Celá kauza s licencemi na GIF začala již v roce 1977, kdy Jacob Ziv a Abraham Lempel publikovali novou metodu určenou pro bezeztrátovou komprimaci údajů. Tuto metodu dále vylepšili a odpublikovali v roce 1978. První metoda je známá pod označením LZ77, druhá LZ78. Není těžké uhodnout, že názvy obou metod pochází z počátečních písmen jmen autorů a roku publikace dané metody. V roce 1983 byla metoda LZ78 rozšířena Terry Welchem, výsledek je celosvětově známý pod označením LZW. Důležité přitom je, že v článku o LZW, který vyšel v IEEE Computer, není ani zmínka o tom, že by metoda byla patentována. V USA je totiž možné patentovat publikované technologie zpětně, a to až s ročním zpožděním – tj. nějakou věc publikujete a až za rok ji můžete patentovat! Další zajímavá (a pro úředníky patentového úřadu ostudná) věc nastala ve chvíli, když si stejnou metodu nechala zapatentovat i IBM, konkrétně autoři Victor Miller a Mark Wegman. Firma IBM dokonce byla o tři týdny rychlejší a získala patent dříve než Terry Welch, resp. jeho zaměstnavatel – firma Sperry, později Unisys. Tato firma se později „postarala“ o velkou popularizaci GIFu, bohužel však v negativním smyslu.

Dodám jen, že patent IBM na LZW komprimaci je v USA přihlášen pod číslem 4,814,746 a patent Unisysu má číslo 4,558,302.

Pojďme si nyní říci, jak celá kauza probíhala. Před vlastním popisem musím říci, že jsem vycházel z několika informačních zdrojů, které se liší v některých detailech a zejména v přesných datech jednotlivých událostí (také však v postojích autora). Snažil jsem se posoudit věrohodnost všech materiálů, ale je možné, že se v dalším textu vyskytnou odchylky od skutečného průběhu událostí. Patrně nejpřesnější popis je možné najít na adrese http://cloanto­.com/users/mcb/199501­27giflzw.html.

4. Stručný přehled celé kauzy

„They want everything to be free and let's all be friends.
But fortunately, this is not the American way.“
 – Unisys patent lawyer Mark Starr, on his company's attempts to squeeze dough out of Websites that dare to generate GIF images, The Industry Standard, 25 April 2000 )

Již víme, že první verze formátu GIF byla vytvořena v roce 1987. V té době však již po čtyři roky platil dvojí patent na komprimační algoritmus LZW (samotní autoři však z tohoto patentu nic nemají). Tvůrci GIFu, tj. firma CompuServe, si však tohoto patentu nevšimla a ani autoři aplikací využívajících GIFy si zpočátku neuvědomili, že používají patentovaný algoritmus. Co je na věci nejzajímavější – prý si toho nevšimli ani pracovníci držitele patentu, tj. firmy Unisys. Po poměrně dlouhou dobu tak mohli jak velcí, tak i malí vývojáři LZW v GIFech používat bez nutnosti placení licenčních poplatků.

První náznaky, že GIF může být zatížen patentem, se objevily v roce 1988, kdy jeden vývojář přerušil práci na toolkitu pro GIF právě z důvodu nejasnosti ohledně licenčních poplatků, pro ostatní svět však tato informace zůstala utajena. V říjnu roku 1989 se v časopise Dr. Dobb's Journal (viz literaturu) objevil článek o LZW, na který několik čtenářů reagovalo v tom smyslu, že jde o patentovaný algoritmus, což v článku nebylo uvedeno. Stále však nikdo explicitně neuvedl do spojitosti GIF, LZW a patenty. V březnu roku 1991 se v časopisu Byte objevil současně popis GIFu a LZW a padla zde pravděpodobně první veřejná informace o možném zatížení grafického formátu GIF patentem. Firma Unisys však stále o GIFu „nevěděla“, což dokazuje i zážitek jednoho z vývojářů, který se přímo v této firmě na patenty a případné licenční poplatky ptal:

„Believe me, you DO own a patent on LZW; who do we talk about LICENCING?“

V prosinci 1994 (prý kolem 28. prosince, tj. uprostřed vánočních svátků) došlo k dohodě mezi Unisysem a CompuServe, objevily se však informace o tom, že CompuServe o patentech věděla již v lednu 1993 – to mnozí vývojáři považovali za podvod, protože cca rok vyvíjeli nástroje pro GIF, aniž by byli informováni o možnosti platby za licence. Licenční politika ohledně GIFu byla oficiálně zveřejněna dne 27. ledna 1995 a mimo jiné v ní byla uvedena tato pravidla:

1. Za každý prodaný SW s implementovaným LZW by se mělo Unisysu platit 0,45% celkové ceny
2. Minimální poplatek je 0,1 dolaru
3. Maximální poplatek je 10 dolarů
4. Poplatky se vybírají za SW vyrobený od začátku roku 1995
5. Současně platí, že poplatky se vybírají pouze při prodeji komerčního software, nikoli freeware

Již tato podoba licenční politiky vyvolala poměrně velké diskuse a objevují se o ní i první zmínky v neodborném tisku, například v magazínu Time. Je to logické, protože v této době byl již GIF široce používán na Internetu. Stále se však nejednalo o větší problém, protože větší společnosti byly ochotny licenční poplatky splácet a vývojářům freeware se tato povinnost vyhnula.

Později však Unisys licenci změnil. Placená licence byla nutná nejenom pro nový SW (od roku 1995), ale i pro CD a knihy obsahující starší SW, pokud toto bylo vytvořeno v roce 1995 a později. Dokonce bylo nutné poplatky platit po každém updatu, což se již výrazně dotklo menších vývojářů. Některé firmy svoje produkty dodávaly bez podpory GIFu, tuto podporu si však bylo možné zadarmo stáhnout – tím byl placený SW osvobozen od poplatků, současně to však Unisys donutilo k dalšímu velmi kontroverznímu kro­ku:

Opět se (již podruhé) změnila licenční politika, a to tak, že platba poplatků byla rozšířena i na nekomerční produkty. V některých případech Unisys vyžadoval jednorázový licenční poplatek ve výši 5000 dolarů za jeden produkt a pro software šířený zadarmo se počítalo s 0,1 dolaru za každý dodaný kus. To prakticky vyloučilo všechny aplikace šířené pod licencí GPL (a podobnými licencemi), protože nebylo jasné, kdo přesně by měl za produkt platit (tvůrce aplikace přece nemusí a ani nemůže spočítat, kolik lidí jeho produkt používá). V případě shareware musel mít tento 30denní limit a podpora GIF musela být zakázána až do času registrace. Podle právníků dokonce existovala reálná možnost stíhání koncových uživatelů (!) v případě, že by si koupili aplikaci, jejíž tvůrce licenční poplatky nezaplatil.

Samozřejmě, že takto nastavená licenční politika vyvolala na Internetu i v tisku doslova bouři. Asi nejproslulejší je akce „Burn All GIFs“, kdy obrázky na některých webových serverech byly hromadně převáděny na formát JPEG. V této chvíli se však ukazuje, že GIF je pro mnohé oblasti nenahraditelný, neboť JPEG kvůli DCT transformaci a ztrátové kompresi není vhodný například pro ukládání pérovek, grafů a „manažerské“ grafiky obecně.

5. Better, smaller, more extensible, and FREE

Firma CompuServe zahajuje dne 16.1.1995 práci na novém formátu GIF, tentokrát nezatíženém patenty. Původně se mluvilo o jménu GIF24, vše však dopadlo poněkud jinak (a podle mě lépe, neboť vytvořený formát není na CompuServe ani jinou firmu vázaný). Thomas Boutell zahájil na Internetu mezi odbornou veřejností diskusi o novém grafickém formátu, původně nazvaném PBF, Portable Bitmap Format. Během cca jednoho týdne se rozeběhla živá e-mailová a newsová korespondence, jak by měl formát vypadat, dokonce se uvažovalo o nekomprimovaných bitmapách zabalených pomocí GZIPu (mnozí si dodnes myslí, že PNG takto ve skutečnosti vypadá). Nakonec se odborníci shodli na formátu založeném na pojmenovaných blocích zabezpečených CRC, možnosti použití plného alfa kanálu pro uložení průhlednosti pixelů, bitovou hloubkou až 48bpp a použití filtrů před aplikací komprimačního algoritmu.

Nový formát byl nazván PNG, což oficiálně znamená Portable Network Graphics, ale v kontextu doby zkratka znamenala celkem výstižně Png is Not Gif (podobnou rekurznivní podobu má ostatně i GNU – GNU is Not Unix). PNG byl poměrně rychle přijat jako standard: 1.6.1996 jako W3C Proposed Recommendation, 11.6.1996 jako RFC, prvního října 1996 ho konečně schválilo a doporučilo W3C a čtrnáctého října 1996 IANA oficiálně zavedla nový MIME typ image/png.

6. Kauza se vytrácí do ztracena

V USA byla účinnost patentu Unisysu zrušena dne 19. června 2003 přesně v 0:00. V dalších zemích, například v Evropě (Německo, Velká Británie, Francie, Itálie) či Japonsku patent vypršel o rok později, tj. o půlnoci mezi 18. a 19. červnem 2004. Poslední známý patent vztahující se ke GIFu vyprší dne 11.8.2006 – to je také důvod vydání tohoto článku (tento patent vlastní IBM). Od začátku příštího týdne je tedy možné grafický formát GIF bez omezení používat, vytvářet (zapisovat) i číst. Pravděpodobně to bude mít negativní dopad na větší rozšíření formátů PNG a MNG („animovaný PNG“), protože pro úspěšné rozšíření těchto formátů je nutné, aby je akceptovali tvůrci všech grafických webových prohlížečů, což je dnes splněno pouze částečně.

Okolo roku 1999, kdy se povinnost platit licenční poplatky za každý program vytvářející GIFy, rozšířila i na programy šířené zadarmo, se vývojáři rozdělili na dvě skupiny. Jedna skupina tvrdila, že celá situace povede k plošnému přechodu z GIFu na PNG, druhá skupina tvrdila, že než se stačí PNG dostatečně rozšířit, patenty na GIF přestanou platit. Ukazuje se, že pravdu měla spíše druhá skupina, a to zejména z toho důvodu, že PNG chybí některé klíčové vlastnosti GIFu, zejména možnost zobrazení jednoduchých animací.

7. Důsledky a poučení

Celá „kauza GIF“ ukázala na některé závažné problémy, které se týkají patentů na software. Problematická je již skutečnost, že jeden algoritmus byl patentován dvakrát, což ostatně vypovídá o kvalitě úředníků na patentových úřadech a tím pádem i o kvalitě přijímaných patentů obecně.

Dále je zajímavé tvrzení Unisysu, že se patent (a tím i licenční poplatky) mohou týkat i dekomprimace, tj. všech prohlížečů. Mnoho právníků se však vyjádřilo v tom smyslu, že patent dekomprimaci explicitně nezmiňuje a Unisys nakonec v této oblasti žádné další kroky neprovedl – to by mělo dopad zejména na tvůrce webových prohlížečů.

Další – a podle mého názoru zcela chybné a lživé – je tvrzení právníků Unisysu, že patent pokrývá jakoukoli metodu, která vede k vytvoření korektního GIFu. Bylo totiž navrženo a úspěšně odzkoušeno několik postupů, které vytvářely validní GIFy, aniž by byl použit algoritmus LZW. Tyto postupy byly založeny například na AVL stromech nebo upravené RLE. Tvrzení „když to vypadá jako výsledek LZW, pak to je LZW“ pokulhává v tom smyslu, že algoritmus LZW (alespoň ta varianta, která je implementována v GIFu) není jednoznačný, tj. existuje nekonečně mnoho způsobů, jakým je možné jeden obrázek zakódovat tak, že se stále jedná o validní GIF.

V dnešní době existuje cca 350 patentů pokrývajících různé způsoby bezeztrátové komprimace rastrových dat (bitmap, pixmap). Ke ztrátové komprimaci existuje cca 100 patentů, včetně jednoho patentu, který se dotýká dalšího velmi známého a používaného formátu – JPEGu. Je tedy velmi pravděpodobné, že jednotliví vývojáři či menší firmy prakticky nemají šanci vytvořit souborový či přenosový formát tak, aby byl ode všech patentů osvobozen; je totiž dobře známo, že texty patentů jsou záměrně nekonkrétní a nejednoznačné, takže jeden patent je možné s dobrým právníkem uplatnit na mnoho různých implementací a technologií.

Poslední poučení plyne se samotných kroků firmy Unisys, které se až podezřele podobají krokům jiných firem, například v oblasti souborových systémů (netřeba jmenovat). Jedná se o to, že držitel patentu nejprve licenční poplatky po určitou dobu nevyžaduje, takže se produkty patenty využívající rozšíří a daná technologie se ve světě uplatní mnohem více, než by tomu bylo v případě technologie, u níž by byly licenční poplatky vybírány ihned (to je například důvod skomírání fraktální komprimace obrazů). Toto pozdní uplatňování licenčních požadavků vede k tříštění standardů, protože mnoho firem a jednotlivců prostě poplatky platit nebude a místo toho vyvine vlastní řešení.

I zde se ukazuje známý fakt, že patenty na software vyhovují velkým korporacím, které mají peníze jak na zaplacení licencí, tak i pracovníků „pátrajících“ na patentových úřadech, a malé firmy či jednotlivé vývojáře naopak softwarové patenty utlačují. Vliv na to má i nesmyslná doba trvání patentů – vždyť 20 let je v oblasti informačních technologií obrovský časový úsek, což ostatně ukazuje i prudký rozmach GIFu v prvních sedmi letech své existence.

8. Literatura a odkazy na Internetu

1. http://burnallgif­s.org – Burn All GIFs Day (slavné stránky tak, jak vypadají dnes)
2. http://burnallgif­s.org/archives/ – Burn All GIFs Day (historická verze)
3. http://patenty­.modry.cz/zaji­cek/netem03.txt – jeden z nejznámějších českých ohlasů na problémy s patenty
4. http://cloanto­.com/users/mcb/199501­27giflzw.html – The GIF Controversy: A Software Developer's Per­spective
5. http://member­s.aol.com/roy­alef/gif87a.txt – specifikace GIF87a
6. http://member­s.aol.com/roy­alef/gif89a.txt – specifikace GIF89a
7. http://member­s.aol.com/roy­alef/gifabout­.htm – All About GIF89a
8. Steve Apiki: „Lossless Data Compression“, Byte, March 1991, pages 309–314
9. Mark Nelson: „LZW Data Compression“, Dr. Dobb's Journal, October 1989, pages 29–36, 86–87
10. Mark Nelson: „LZW Patent Issues“, Dr. Dobb's Journal, December 1989, pages 8–12
11. Terry Welch: „A technique for high-performance data compression“, IEEE Computer, June 1984, pages 8–19
    (popis algoritmu známého jako LZW)
12. Jacob Ziv, Abraham Lempel: „A universal algorithm for sequential data compression“, IEEE Transactions on Information Theory, May 1977, pages 337–343
    (popis algoritmu známého jako LZ77)
13. Jacob Ziv, Abraham Lempel: „Compression of individual sequences via variable-rate coding“, IEEE Transactions on Information Theory, September 1987, pages 530–536
    (popis algoritmu známého jako LZ78)

9. O čem si povíme příště

V navazujícím článku si uvedeme některé zajímavé technické informace o formátu GIF, zejména se zmíním o již dlouho tradovaném mýtu o maximálním počtu barev použitých v jednom obrázku. Ukážeme si i další poměrně neznámé vlastnosti GIFu, například možnost ukládání slideshow do jednoho souboru.