Keskustelu: Koodit: Python: GIF-tiedostojen käsittely

"""Purkaa ja pakkaa GIF-tiedostoja. Versio 1.42.

Tässä ohjelmassa käytetyt GIF-tiedostomuotoon liittyvät lyhenteet:
    LSD: Logical Screen Descriptor; tiedot piirtoalueesta, jolle kaikki GIF:in
          sisältämät kuvat piirretään
    GCT: Global Color Table; yksi paletti, jota voivat käyttää kaikki GIF:in
          sisältämät kuvat
    LCT: Local Color Table; GIF:in sisältämän yksittäisen kuvan oma paletti
    LZW: Lempel-Ziv-Welch, GIF:in kuvadatan pakkausalgoritmi"""

import math
import os
import struct
import sys
import time

# paletin bittisyys LZW-koodauksessa vähintään (2...8, yleensä 2);
# huom.: LZW-koodien minimipituus on yhtä suurempi
MIN_LZW_PALETTE_BITS = 2
# LZW-koodien maksimipituus pakattaessa (9...12, yleensä 12)
MAX_LZW_ENCODE_BITS = 12
# paljonko tietoa tulostetaan (0 = vain virheet, 1 = vähän, 2 = paljon)
VERBOSITY = 0

# ohjeteksti
HELP_TEXT = """\
Purkaa GIF-tiedoston RGB-raakadataksi tai pakkaa RGB-raakadatan GIF:iksi.
(RGB-raakadatan tavut: R,G,B,R,G,B,...; tiedostopääte .data GIMP:issä.)

Komentoriviparametrit purettaessa: LÄHDE KOHDE
    LÄHDE  luettava GIF-tiedosto
    KOHDE  kirjoitettava RGB-raakadatatiedosto

Komentoriviparametrit pakattaessa: LÄHDE LEVEYS KOHDE
    LÄHDE   luettava RGB-raakadatatiedosto
    LEVEYS  luettavan kuvan leveys pikseleinä
    KOHDE   kirjoitettava GIF-tiedosto"""

# --- Purku & pakkaus -----------------------------------------------------------------------------

def read_bytes(handle, length):
    """Lue tavuja tiedostosta tai anna virheilmoitus, jos tiedosto loppuu kesken."""

    data = handle.read(length)
    if len(data) < length:
        raise Exception("EOF")
    return data

def skip_bytes(handle, length):
    """Ohita tavuja tiedostossa tai anna virheilmoitus, jos tiedosto loppuu kesken."""

    origPos = handle.tell()
    handle.seek(length, 1)
    if handle.tell() - origPos < length:
        raise Exception("EOF")

def read_subblocks(handle):
    """Lue alilohkoihin kääritty data tiedostokahvan nykyisestä sijainnista alkaen.
    handle: tiedostokahva. Palautusarvo: data ilman alilohkokäärettä."""

    # Alilohkoissa on ensin pituustavu ja sitten sen mukainen määrä varsinaisia
    # datatavuja. Viimeinen alilohko on pituudeltaan nolla.

    data = bytearray()
    subblockSize = read_bytes(handle, 1)[0]  # ensimmäisen alilohkon koko

    while subblockSize:
        chunk = read_bytes(handle, subblockSize + 1)
        data.extend(chunk[:-1])   # alilohkon sisältö
        subblockSize = chunk[-1]  # seuraavan alilohkon koko

    return bytes(data)

def skip_subblocks(handle):
    """Ohita alilohkoihin kääritty data tiedostokahvan nykyisestä sijainnista alkaen.
    handle: tiedostokahva."""

    # Katso myös aliohjelman read_subblocks() kommentit.

    subblockSize = read_bytes(handle, 1)[0]  # ensimmäisen alilohkon koko

    while subblockSize:
        skip_bytes(handle, subblockSize)         # ohita sisältö
        subblockSize = read_bytes(handle, 1)[0]  # seuraavan alilohkon koko

def format_palette(palette):
    """Muotoile paletti tulostettavaksi."""

    return ",".join(
        "".join(f"{c:02x}" for c in palette[i*3:(i+1)*3])
        for i in range(len(palette) // 3)
    )

# --- Purku ---------------------------------------------------------------------------------------

def read_image_info(handle):
    """Lue GIF-tiedoston yksittäisen kuvan perustiedot.
    handle: tiedostokahva; huom.: sijainnin pitää olla valmiiksi Image Descriptorin
    tyyppitavun (",") jälkeisessä tavussa.
    Palautusarvo: dict:
        width     : kuvan leveys  pikseleinä (1...65535)
        height    : kuvan korkeus pikseleinä (1...65535)
        interlace : onko kuva lomitettu (bool)
        palAddr   : LCT:n alkuosoite (None = ei LCT:tä)
        palBits   : LCT:n bittisyys  (1...8; None = ei LCT:tä)
        LZWPalBits: paletin (GCT/LCT) bittisyys LZW-koodauksessa (2...8)
        LZWAddr   : LZW-datan alkuosoite tiedostossa"""

    # lue loput Image Descriptorista
    (width, height, packedFields) = struct.unpack("<4x2HB", read_bytes(handle, 9))

    if min(width, height) == 0:
        raise Exception("IMAGE_AREA_ZERO")  # kuvan ala on nolla

    # jos kuvalla on LCT, ota muistiin sen osoite ja bittisyys sekä ohita se toistaiseksi
    if packedFields >> 7:
        palAddr = handle.tell()
        palBits = (packedFields & 7) + 1
        skip_bytes(handle, 2 ** palBits * 3)
    else:
        palAddr = None
        palBits = None

    LZWPalBits = read_bytes(handle, 1)[0]  # paletin bittisyys LZW-koodauksessa
    if not 2 <= LZWPalBits <= 11:
        raise Exception("INVALID_LZW_PALETTE_BITS")

    LZWAddr = handle.tell()  # ota muistiin LZW-kuvadatan alkuosoite
    skip_subblocks(handle)   # ohita LZW-kuvadata

    return {
        "width":      width,
        "height":     height,
        "interlace":  bool((packedFields >> 6) & 1),
        "palAddr":    palAddr,
        "palBits":    palBits,
        "LZWPalBits": LZWPalBits,
        "LZWAddr":    LZWAddr,
    }

def skip_image(handle):
    """Ohita yksittäinen kuva GIF-tiedostossa.
    handle: tiedostokahva; huom: sijainnin pitää olla valmiiksi Image Descriptorin
    tyyppitavun (",") jälkeisessä tavussa."""

    # lue loput Image Descriptorista, ota packedFields-tavu
    packedFields = read_bytes(handle, 9)[8]

    # ohita mahdollinen LCT
    if packedFields >> 7 == 1:
        palBits = (packedFields & 0b111) + 1
        paletteSize = 2 ** palBits * 3
        skip_bytes(handle, paletteSize)

    skip_bytes(handle, 1)   # ohita tavu, jossa on paletin bittisyys LZW-koodauksessa
    skip_subblocks(handle)  # ohita LZW-kuvadata

def skip_extension_block(handle):
    """Ohita Extension-lohko (paitsi tulosta kommenttiteksti).
    handle: tiedostokahva; huom.: sijainnin pitää olla valmiiksi Extension Introducer
    -tavun ("!") jälkeisessä tavussa."""

    extensionLabel = read_bytes(handle, 1)[0]  # lohkon alityyppi (Extension Label)

    if extensionLabel == 0x01:  # Plain Text Extension
        skip_bytes(handle, 13)
        skip_subblocks(handle)
    elif extensionLabel == 0xf9:  # Graphic Control Extension
        skip_bytes(handle, 6)
    elif extensionLabel == 0xfe:  # Comment Extension
        text = read_subblocks(handle).decode("ascii", errors="backslashreplace")
        print(f'Kommenttiteksti: "{text}"')
    elif extensionLabel == 0xff:  # Application Extension
        skip_bytes(handle, 12)
        skip_subblocks(handle)
    else:
        raise Exception("INVALID_EXTENSION_LABEL")

def read_GIF_blocks(handle):
    """Käy GIF-tiedoston lohkot läpi (poislukien Header, LSD, GCT).
    handle: tiedostokahva; huom: sijainnin pitää olla valmiiksi LSD:n tai
    mahdollisen GCT:n jälkeisessä tavussa.
    Palauta tiedoston ensimmäisen kuvan tiedot (katso read_image_info())
    tai None, jos kuvia ei ollut yhtään."""

    firstImageInfo = None  # ensimmäisen kuvan tiedot

    while True:
        blockType = read_bytes(handle, 1)  # lohkon tyyppi

        if blockType == b",":  # kuvan tiedot (Image Descriptor)
            if firstImageInfo is None:
                firstImageInfo = read_image_info(handle)  # lue ensimmäinen
            else:
                skip_image(handle)  # ohita muut
        elif blockType == b"!":  # Extension
            skip_extension_block(handle)
        elif blockType == b";":  # Trailer
            return firstImageInfo
        else:
            raise Exception("INVALID_BLOCK_TYPE")

def read_GIF(handle):
    """Lue GIF-tiedoston perustiedot, jotka voidaan antaa muille funktioille
    koko tiedoston lukemiseksi. Huom.: jos tiedosto sisältää useamman kuvan,
    palauta vain ensimmäisen kuvan tiedot.
    handle: tiedostokahva.
    Palautusarvo: dict:
        width     : kuvan leveys  pikseleinä (1...65535)
        height    : kuvan korkeus pikseleinä (1...65535)
        interlace : onko kuva lomitettu (bool)
        palAddr   : paletin (GCT/LCT) alkuosoite
        palBits   : paletin (GCT/LCT) bittisyys (1...8)
        LZWPalBits: paletin (GCT/LCT) bittisyys LZW-koodauksessa (2...8)
        LZWAddr   : kuvadatan alkuosoite tiedostossa"""

    handle.seek(0)

    # lue Header ja LSD
    (id_, version, packedFields) = struct.unpack("<3s3s4xB2x", read_bytes(handle, 13))

    if id_ != b"GIF":
        raise Exception("NOT_A_GIF_FILE")  # ei GIF-tiedosto
    if version not in (b"87a", b"89a"):
        print("Varoitus: tuntematon GIF:in versio.", file=sys.stderr)

    # jos GCT on, ota muistiin osoite ja bittisyys sekä ohita
    if packedFields >> 7:
        palAddr = handle.tell()
        palBits = (packedFields & 7) + 1
        skip_bytes(handle, 2 ** palBits * 3)
    else:
        palAddr = None
        palBits = None

    imageInfo = read_GIF_blocks(handle)  # tiedoston ensimmäisen kuvan tiedot

    if imageInfo is None:
        raise Exception("NO_IMAGES_IN_FILE")  # tiedostossa ei ole kuvia

    if imageInfo["palAddr"] is not None:
        # kuvalla on LCT; käytä sitä GCT:n sijasta
        palAddr = imageInfo["palAddr"]
        palBits = imageInfo["palBits"]
    elif palAddr is None:
        raise Exception("NO_PALETTE")  # ei LCT:tä eikä GCT:tä

    return {
        "width":      imageInfo["width"],
        "height":     imageInfo["height"],
        "interlace":  imageInfo["interlace"],
        "palAddr":    palAddr,
        "palBits":    palBits,
        "LZWPalBits": imageInfo["LZWPalBits"],
        "LZWAddr":    imageInfo["LZWAddr"],
    }

def decode_LZW_data(LZWData, palBits):
    """Pura LZW-kuvadata.
    LZWData: tavujono, palBits: paletin bittisyys LZW-koodauksessa (2...8).
    Generoi indeksoitu kuvadata tavujonoina (1 tavu/pikseli)."""

    # Purettava data koostuu koodeista:
    # - pituus:
    #   - vaihtelee
    #   - vähintään palBits+1 (3...9) bittiä
    #   - enintään 12 bittiä
    # - bittijärjestys: esimerkki tavujen muuntamisesta koodeiksi:
    #   datan ensimmäiset tavut: ABCDEFGH, IJKLMNOP, QRSTUVWX
    #   -> 6-bittiset koodit:    CDEFGH, MNOPAB, WXIJKL, QRSTUV
    #   EI siis esim. seuraavasti:
    #     - CDEFGH, ABMNOP, IJKLWX, QRSTUV (väärin!)
    #     - ABCDEF, GHIJKL, MNOPQR, STUVWX (väärin!)
    #     - ABCDEF, IJKLGH, QRMNOP, STUVWX (väärin!)
    # - ensimmäisenä alustuskoodi
    # - viimeisenä loppukoodi

    # Purkuohjelman sisäinen tila:
    # - seuraavan koodin pituus purettavassa datassa:
    #   - vähintään palBits+1 (3...9) bittiä
    #   - enintään 12 bittiä
    # - sanakirja:
    #   - kukin sana: tavujono
    #   - alustetun sanakirjan sanat:
    #     - ensimmäiset 4/8/16/32/64/128/256 (riippuen palBits:in arvosta):
    #       yksi pikseli kutakin väriä (indeksiä)
    #     - alustuskoodi (arvolla ei väliä)
    #     - loppukoodi   (arvolla ei väliä)
    #   - loput sanat: usean pikselin yhdistelmät
    #   - yhteensä enintään 4096 (2**12) sanaa

    if VERBOSITY >= 2:
        print("LZW-purkuloki (tavuosoite, bittiosoite, koodin pituus, sanakirjan koko, koodi):")

    # vakiot
    clearCode      = 2 ** palBits      # koodi, jolla alustetaan LZW-sanakirja
    endCode        = 2 ** palBits + 1  # koodi, jolla data loppuu
    initialDictLen = 2 ** palBits + 2  # alustetun sanakirjan koko
    minCodeLen     = palBits + 1       # koodien minimipituus (3...9 bittiä)

    # muuttujat
    bytePos   = 0           # tavuja luettu kuvadatasta
    bitPos    = 0           # bittejä luettu seuraavasta tavusta (0...7)
    codeLen   = minCodeLen  # koodien nykyinen pituus bitteinä
    prevEntry = None        # edellinen sanakirjan sana
    # sanakirja; indeksi = koodi,
    # arvo = sana: (koodiviittaus joka muodostaa alun, lopputavu);
    # huom.: alustus- ja loppukoodin arvoilla ei ole väliä
    LZWDict = [(-1, i) for i in range(initialDictLen)]

    # tilastoja varten
    maxCodeLen = minCodeLen
    codeCount = 0
    clearCodeCount = 0
    pixelCount = 0
    uniqueColors = set()

    while True:
        if bitPos + codeLen > (len(LZWData) - bytePos) * 8:
            raise Exception("EOF")  # kuvadata loppui kesken

        # lue koodi jäljellä olevan datan alusta
        code = LZWData[bytePos]
        if codeLen > 8 - bitPos:
            code |= LZWData[bytePos+1] << 8
            if codeLen > 16 - bitPos:
                code |= LZWData[bytePos+2] << 16
        code >>= bitPos
        code &= (1 << codeLen) - 1

        if VERBOSITY >= 2:
            print(",".join(str(n) for n in (bytePos, bitPos, codeLen, len(LZWDict), code)))
        codeCount += 1

        # siirry datassa eteenpäin
        bytePos += (bitPos + codeLen) // 8
        bitPos  =  (bitPos + codeLen) %  8

        if code == clearCode:
            # sanakirjan alustus
            LZWDict = LZWDict[:initialDictLen]
            codeLen = minCodeLen
            prevCode = None
            clearCodeCount += 1
        elif code == endCode:
            # datan loppu
            break
        else:
            # sanakirjan sana
            if prevCode is not None:
                # lisää sanakirjaan sana, joka koostuu edellisestä sanasta ja
                # koodin mukaisen sanan ensimmäisestä tavusta
                if code < len(LZWDict):
                    suffixCode = code
                elif code == len(LZWDict):
                    suffixCode = prevCode
                else:
                    raise Exception("INVALID_LZW_CODE")
                # hae koodin mukaisen sanan ensimmäinen tavu
                while suffixCode != -1:
                    (suffixCode, suffixByte) = LZWDict[suffixCode]
                LZWDict.append((prevCode, suffixByte))
                prevCode = None
            if code < len(LZWDict) < 2 ** 12:
                # nykyinen sana muistiin
                prevCode = code
            if len(LZWDict) == 2 ** codeLen and codeLen < 12:
                # lisää koodien pituutta
                codeLen += 1
                maxCodeLen = max(maxCodeLen, codeLen)
            # muunna sana tavujonoksi ja generoi se
            entry = bytearray()
            while code != -1:
                (code, byte) = LZWDict[code]
                entry.append(byte)
                uniqueColors.add(byte)
            yield entry[::-1]
            pixelCount += len(entry)

    if VERBOSITY >= 1:
        sizeBits = bytePos * 8 + bitPos
        print("LZW-kuvadata purettu:")
        print(f"  bittejä              : {sizeBits}")
        print(f"  koodeja              : {codeCount}")
        print(f"  alustuskoodeja       : {clearCodeCount}")
        print(f"  pikseleitä           : {pixelCount}")
        print(f"  paletin koodaus      : {palBits}-bittinen")
        print(f"  eri paletti-indeksejä: {len(uniqueColors)}")
        print(f"  bittiä/koodi         : {sizeBits/codeCount:.2f}")
        print(f"  bittiä/pikseli       : {sizeBits/pixelCount:.2f}")
        print(f"  pikseliä/koodi       : {pixelCount/codeCount:.2f}")
        print(f"  koodien minimipituus : {minCodeLen} bittiä")
        print(f"  koodien maksimipituus: {maxCodeLen} bittiä")

def deinterlace_image(imageData, width):
    """Poista kuvadatasta lomitus vaihtamalla pikselirivien järjestys.
    imageData: indeksoitu kuvadata (tavujono, 1 tavu/pikseli), width: kuvan leveys pikseleinä.
    Palautusarvo: indeksoitu kuvadata (tavujono, 1 tavu/pikseli).

    Lomitetun kuvadatan rakenne:
        osa A: joka 8. rivi alkaen rivistä 0 (0,  8, 16, ...)
        osa B: joka 8. rivi alkaen rivistä 4 (4, 12, 20, ...)
        osa C: joka 4. rivi alkaen rivistä 2 (2,  6, 10, ...)
        osa D: joka 2. rivi alkaen rivistä 1 (1,  3,  5, ...)
    Lomittamattomat rivit tulevat siis 8 rivin jaksoissa seuraavista osista:
        A, D, C, D, B, D, C, D, ..."""

    height = len(imageData) // width

    # miltä riveiltä lomitetun datan osat B, C ja D alkavat
    partBStart = (height + 7) // 8  # = rivejä osassa A
    partCStart = (height + 3) // 4  # = rivejä osissa A ja B
    partDStart = (height + 1) // 2  # = rivejä osissa A, B ja C

    # luo uusi kuvadata, jossa pikselirivien järjestys on vaihdettu;
    # sy = lähderivi, dy = kohderivi
    deinterlacedData = bytearray()
    for dy in range(height):
        if dy % 8 == 0:
            sy = dy // 8
        elif dy % 8 == 4:
            sy = partBStart + dy // 8
        elif dy % 4 == 2:
            sy = partCStart + dy // 4
        else:
            sy = partDStart + dy // 2
        deinterlacedData.extend(imageData[sy*width:(sy+1)*width])

    return bytes(deinterlacedData)

def GIF_to_raw_image(GIFHandle, rawHandle):
    """Muunna GIF-tiedosto raakadatakuvaksi (tavut: R,G,B,R,G,B,...).
    Rajoitukset: katso read_GIF():in kuvaus.
    GIFHandle: luettava tiedostokahva, rawHandle: kirjoitettava tiedostokahva"""

    info = read_GIF(GIFHandle)  # lue perustiedot

    # lue paletti (GCT tai LCT; tavuja muodossa RGBRGB...)
    GIFHandle.seek(info["palAddr"])
    palette = read_bytes(GIFHandle, 2 ** info["palBits"] * 3)

    if VERBOSITY >= 1:
        uniqueColorCount = len(set(
            palette[i*3:(i+1)*3] for i in range(len(palette) // 3)
        ))
        print(f"Puretaan {os.path.basename(GIFHandle.name)}:")
        print(f"  leveys              : {info['width']}")
        print(f"  korkeus             : {info['height']}")
        print(f"  lomitettu           : {['ei','kyllä'][info['interlace']]}")
        print(f"  paletti             : {info['palBits']}-bittinen")
        print(f"  eri värejä paletissa: {uniqueColorCount}")
        if VERBOSITY >= 2:
            print("Paletti:", format_palette(palette))

    # lue LZW-kuvadata
    GIFHandle.seek(info["LZWAddr"])
    imageData = read_subblocks(GIFHandle)

    # pura LZW-kuvadata muotoon 1 tavu/pikseli
    imageData = b"".join(decode_LZW_data(imageData, info["LZWPalBits"]))

    if info["palBits"] < 8 and max(imageData) >= 2 ** info["palBits"]:
        # kuvadata sisältää liian suuren indeksin
        raise Exception("INVALID_INDEX_IN_IMAGE_DATA")

    if info["interlace"]:
        imageData = deinterlace_image(imageData, info["width"])  # pura lomitus

    # kirjoita raakadatakuvatiedosto
    rawHandle.seek(0)
    for pixel in imageData:
        rawHandle.write(palette[pixel*3:(pixel+1)*3])

# --- Pakkaus -------------------------------------------------------------------------------------

def get_palette_from_raw_image(handle):
    """Luo paletti raakadatakuvalle (tavut: R,G,B,R,G,B,...; enintään 256 väriä).
    handle: tiedostokahva.
    Palauta paletti (tavut: RGBRGB...)"""

    pixelCount = handle.seek(0, 2) // 3  # pikselien määrä tiedostokoosta

    palette = set()
    handle.seek(0)

    for pos in range(pixelCount):
        color = handle.read(3)
        if color not in palette:
            if len(palette) == 256:
                raise Exception("TOO_MANY_COLORS")
            palette.add(color)

    return b"".join(sorted(palette))

def raw_image_to_indexed(handle, palette):
    """Sovita raakadatakuva (tavut: R,G,B,R,G,B,...; enintään 256 väriä) palettiin.
    handle: tiedostokahva, palette: paletti (tavut: RGBRGB...)
    Palauta indeksoitu kuvadata (1 tavu/pikseli)."""

    # RGB -> indeksi
    RGBToIndex = dict((palette[i*3:(i+1)*3], i) for i in range(len(palette) // 3))

    pixelCount = handle.seek(0, 2) // 3  # pikselien määrä tiedostokoosta
    handle.seek(0)
    imageData = bytearray()

    for pos in range(pixelCount):
        imageData.append(RGBToIndex[handle.read(3)])

    return imageData

def get_palette_bits(colorCount):
    """Laske, montako bittiä värien koodaamiseen tarvitaan.
    colorCount: värien määrä (1...256).
    Palautusarvo: bittien määrä (1...8)."""

    # 2-kantainen logaritmi pyöristettynä ylöspäin, kuitenkin vähintään 1
    return max(math.ceil(math.log2(colorCount)), 1)

def encode_LZW_data(palette, imageData):
    """Pakkaa kuvadata LZW:ksi. Parametrit:
        palette: paletti (tavut: RGBRGB...)
        imageData: indeksoitu kuvadata (1 tavu/pikseli)
    Generoi pakattu kuvadata tavuina."""

    # katso kommentit decode_LZW_data():ssa

    if VERBOSITY >= 2:
        print("LZW-pakkausloki (pikseliosoite, koodin pituus, sanakirjan koko, koodi):")

    # vakiot
    # paletin bittisyys LZW-koodauksessa (2...8; GIF ei tue 1:ä)
    palBits = max(get_palette_bits(len(palette) // 3), MIN_LZW_PALETTE_BITS)
    palSize = clearCode = 2 ** palBits      # paletin koko ja LZW-alustuskoodi
    endCode             = 2 ** palBits + 1  # LZW-loppukoodi
    minCodeLen          = palBits + 1       # LZW-koodien minimipituus (3...9 bittiä)

    # muuttujat
    inputPos = 0          # sijainti luettavassa kuvadatassa
    codeLen = minCodeLen  # LZW-koodien pituus
    LZWByte = 0           # seuraavaksi kirjoitettava tavu
    LZWBitPos = 0         # LZWByte:n koko bitteinä
    # sanakirja: {sana: koodi, ...}; huom.: ei sisällä alustus- ja loppukoodeja,
    # joten koko on oikeasti kahta suurempi
    LZWDict = dict((bytes((i,)), i) for i in range(palSize))

    # tilastoja varten
    maxCodeLen = minCodeLen
    codeCount = 0
    clearCodeCount = 0
    outputByteCount = 0

    # kirjoita alustuskoodi
    LZWByte = clearCode
    LZWBitPos = codeLen
    while LZWBitPos >= 8:
        yield LZWByte & 0xff
        outputByteCount += 1
        LZWByte >>= 8
        LZWBitPos -= 8
    clearCodeCount += 1

    while inputPos < len(imageData):
        # miten pitkä on pisin sanakirjan sana, jolla jäljelläoleva kuvadata alkaa?
        for length in range(1, len(imageData) - inputPos + 1):
            if bytes(imageData[inputPos:inputPos+length]) in LZWDict:
                prefixLen = length
            else:
                break
        # hae kyseistä sanaa vastaava koodi
        code = LZWDict[bytes(imageData[inputPos:inputPos+prefixLen])]

        if VERBOSITY >= 2:
            print(",".join(str(n) for n in (inputPos, codeLen, len(LZWDict) + 2, code)))

        # generoi koodi tavuina
        LZWByte |= code << LZWBitPos
        LZWBitPos += codeLen
        while LZWBitPos >= 8:
            yield LZWByte & 0xff
            outputByteCount += 1
            LZWByte >>= 8
            LZWBitPos -= 8

        if inputPos + prefixLen < len(imageData):
            # ei olla viimeisissä koodattavissa pikseleissä; lisää sana sanakirjaan
            if len(LZWDict) + 2 < 2 ** MAX_LZW_ENCODE_BITS - 1:
                # sanakirjassa on tilaa; lisää koodatut pikselit plus seuraava pikseli
                LZWDict[bytes(imageData[inputPos:inputPos+prefixLen+1])] = len(LZWDict) + 2
                if len(LZWDict) + 2 == 2 ** codeLen + 1:
                    # nykyisellä koodinpituudella ei mahdu lisää koodeja; kasvata sitä
                    codeLen += 1
                    maxCodeLen = max(maxCodeLen, codeLen)
            else:
                # sanakirjassa on tilaa enää alustuskoodille
                # generoi alustuskoodi tavuina
                LZWByte |= clearCode << LZWBitPos
                LZWBitPos += codeLen
                while LZWBitPos >= 8:
                    yield LZWByte & 0xff
                    outputByteCount += 1
                    LZWByte >>= 8
                    LZWBitPos -= 8
                clearCodeCount += 1
                # alusta sanakirja ja koodien pituus
                LZWDict = dict((bytes((i,)), i) for i in range(palSize))
                codeLen = minCodeLen

        inputPos += prefixLen  # siirry juuri koodatun kuvadatan osan yli
        codeCount += 1

    # kirjoita loppukoodi
    LZWByte |= endCode << LZWBitPos
    LZWBitPos += codeLen
    while LZWBitPos > 0:
        yield LZWByte & 0xff
        outputByteCount += 1
        LZWByte >>= 8
        LZWBitPos -= 8

    if VERBOSITY >= 1:
        pixelCount = len(imageData)
        sizeBits = outputByteCount * 8 + LZWBitPos  # LZWBitPos on -7...0
        print("LZW-kuvadata pakattu:")
        print(f"  pikseleitä           : {pixelCount}")
        print(f"  paletin koodaus      : {palBits}-bittinen")
        print(f"  bittejä              : {sizeBits}")
        print(f"  koodeja              : {codeCount}")
        print(f"  alustuskoodeja       : {clearCodeCount}")
        print(f"  bittiä/koodi         : {sizeBits/codeCount:.2f}")
        print(f"  bittiä/pikseli       : {sizeBits/pixelCount:.2f}")
        print(f"  pikseliä/koodi       : {pixelCount/codeCount:.2f}")
        print(f"  koodien minimipituus : {minCodeLen} bittiä")
        print(f"  koodien maksimipituus: {maxCodeLen} bittiä")

def write_GIF(width, height, palette, LZWData, handle):
    """Kirjoita GIF-tiedosto (GIF87a, GCT, yksi kuva). Parametrit:
        width: leveys pikseleinä
        height: korkeus pikseleinä
        palette: paletti (tavut: RGBRGB...)
        LZWData: LZW-pakattu kuvadata ilman alilohkokäärettä (tavujono)
        handle: tiedostokahva"""

    palBits = get_palette_bits(len(palette) // 3)  # paletin bittisyys
    if VERBOSITY >= 1:
        print(f"Kirjoitetaan paletti {palBits}-bittisenä.")

    # täytä paletti mustalla bittien sallimaan maksimiin saakka
    palette = palette + (2 ** palBits * 3 - len(palette)) * b"\x00"

    handle.seek(0)

    # Header ja LSD (käytä GCT:tä)
    packedFields = 0x80 | (palBits - 1)
    handle.write(struct.pack("<6s2H3B", b"GIF87a", width, height, packedFields, 0, 0))

    handle.write(palette)  # GCT

    # Image Descriptor (ei LCT:tä)
    imgDesc = struct.pack("<B4HB", ord(b","), 0, 0, width, height, 0x00)
    handle.write(imgDesc)

    # paletin bittisyys LZW-koodauksessa (2...8; GIF ei tue 1:ä)
    handle.write(bytes((max(palBits, MIN_LZW_PALETTE_BITS),)))

    # kirjoita LZW-kuvadata alilohkoihin (enintään 255 datatavua kuhunkin)
    LZWPos = 0
    while LZWPos < len(LZWData):
        subblockSize = min(255, len(LZWData) - LZWPos)
        handle.write(
            bytes((subblockSize,)) + LZWData[LZWPos:LZWPos+subblockSize]
        )
        LZWPos += subblockSize

    # tyhjä alilohko (nollatavu) ja Trailer (";")
    handle.write(b"\x00;")

def raw_image_to_GIF(rawHandle, width, GIFHandle):
    """Muunna raakadatakuva (tavut: R,G,B,R,G,B,...; enintään 256 väriä)
    GIF-tiedostoksi. Parametrit:
        rawHandle: luettava tiedostokahva
        width: kuvan leveys pikseleinä
        GIFHandle: kirjoitettavan tiedoston kahva"""

    # korkeus ja jakojäännös tiedostokoosta ja leveydestä
    (height, remainder) = divmod(rawHandle.seek(0, 2), width * 3)

    if remainder:
        sys.exit("Lähdetiedoston koko ei ole jaollinen (leveys * 3):lla.")
    if height == 0:
        sys.exit("Lähdetiedosto on tyhjä.")
    if height > 65535:
        sys.exit("Kohdetiedostosta tulisi liian korkea.")

    palette = get_palette_from_raw_image(rawHandle)  # hae paletti

    if VERBOSITY >= 1:
        print(f"Pakataan {os.path.basename(rawHandle.name)}:")
        print(f"  leveys : {width}")
        print(f"  korkeus: {height}")
        print(f"  värejä : {len(palette)//3}")
        if VERBOSITY >= 2:
            print("Paletti:", format_palette(palette))

    imageData = raw_image_to_indexed(rawHandle, palette)  # indeksoi kuvadata
    LZWData = bytes(encode_LZW_data(palette, imageData))  # pakkaa kuvadata

    # kirjoita GIF-tiedosto
    write_GIF(width, height, palette, LZWData, GIFHandle)

# -------------------------------------------------------------------------------------------------

if __name__ == "__main__":
    # aloita ajanotto
    startTime = time.time()

    # lue komentoriviparametrit ja päättele niiden määrästä, mitä tehdään
    if len(sys.argv) == 3:
        decode = True
        (source, target) = sys.argv[1:]
    elif len(sys.argv) == 4:
        decode = False
        (source, width, target) = sys.argv[1:]
        try:
            width = int(width, 10)
            if not 1 <= width <= 65535:
                raise ValueError
        except ValueError:
            sys.exit("Kuvan leveyden pitää olla väliltä 1...65535.")
    else:
        exit(HELP_TEXT)

    if not os.path.isfile(source):
        sys.exit("Lähdetiedostoa ei löydy.")
    if os.path.exists(target):
        sys.exit("Kohdetiedosto on jo olemassa.")

    # avaa tiedostot ja pura tai pakkaa
    try:
        with open(source, "rb") as sourceHnd, open(target, "wb") as targetHnd:
            if decode:
                GIF_to_raw_image(sourceHnd, targetHnd)
            else:
                raw_image_to_GIF(sourceHnd, width, targetHnd)
    except OSError:
        exit("Virhe luettaessa tai kirjoitettaessa tiedostoja.")

    if VERBOSITY >= 1:
        print(f"Aikaa kului {time.time()-startTime:.1f} s.")
        print()