{ Арифметический кодек } {--------------------------------------------------------------------------- (c) Copyright Aleksandrov O.E., 2010 Molecular Physics department, USTU, Ekaterinsburg, K-2, 620002, RUSSIA phone 375-41-46 E-mail: aleks@dpt.ustu.ru (c) Copyright Александров О.Е., 2010 620002, Екатеринбург, К-2, УГТУ, Кафедра молекулярной физики тел. 375-41-46 E-mail: aleks@dpt.ustu.ru ----------------------------------------------------------------------------} Unit AriCodec; {$IfDef NoChecking} {$R-,S-,Q-} {$EndIf Def NoChecking} {$BOOLEVAL OFF - !!! ЭТО НАДО, ибо есть вызовы функций в заголовке while . } INTERFACE USES VeryLongArithmetic , AriTypes , AriBase; type tError=( errOK , errNotInEncodeRegime , errEncodeOutBufferTooSmallForHeader , errDecodeCodeBufferTooSmallForHeaderStatistics , errEncodeNotStarted , errEncodeInBufferEmpty , errOutBufferTooSmallForPortion , errNotInDecodeRegime , errDecodeCodeBufferTooSmallForHeader , errDecodeNotStarted , errDecodeCodeBufferInvalid , errDecodeCodeBufferTooSmallToReadPortionHeader , errDecodeCodeBufferTooSmallToReadPortion , errEncodeNoStatistic ); { Флаг режима работы кодека } tFlag=( fEncodeRegime { кодек в режиме кодирования } , fDecodeRegime , fEncodeRegimeStarted { иникодек в режиме кодирования } , fDecodeRegimeStarted , fAlignStatistic { выравнивание статистики на степень двойки для сдвига вместо деления } ); tFlags=set of tFlag; { Данные для записи статистики символа в выходной поток (буфер) DWORD-счетчики } tOutBuffHeaderStatistic=packed record Symbol:tSymbol; { значение символа } Frequency:longword; { частота } end; { Данные для записи статистики символа в выходной поток (буфер) WORD-счетчики } tOutBuffHeaderShortStatistic=packed record Symbol:tSymbol; { значение символа } Frequency:word; { частота } end; { Массив статистики символа в выходной поток (буфер) } tOutBuffHeaderStatistics=packed array[tSymbol] of tOutBuffHeaderStatistic; tOutBuffHeaderShortStatistics=packed array[tSymbol] of tOutBuffHeaderShortStatistic; tBufferFlag=( bfUseShortStatistic { использовать короткую статистику } , bfVersion0 { версия } , bfVersion1 { версия } , bfVersion2 { версия } , bfReseved0 , bfReseved1 , bfReseved2 , bfReseved3 ); tBufferFlags=set of tBufferFlag; const cVersion=[bfVersion0]; cVersionMask=[bfVersion0..bfVersion2]; type { Заголовок буфера выходного потока} tOutBufferHeader=packed record Flags:tBufferFlags; StatisticsLastElement:tSymbol; { последний элемент массива Statistics, нумерация с 0 } case boolean of { элементы массива Statistics не длиннее Word } FALSE: (Statistics:tOutBuffHeaderStatistics); { статистика размера DWORD } TRUE: (ShortStatistics:tOutBuffHeaderShortStatistics); { статистика размера WORD } end; { Данные для записи ПОРЦИИ упакованной информации в выходной поток (буфер) } { количество упакованных символов. 0 означает конец буфера } tPackedSymbolCount=word; { запись КОДА в буфере } tPackedPortion=packed record EncodedSymbolCount:tPackedSymbolCount; { количество упакованных символов. 0 означает конец буфера } CodeData:tVeryLongUIntEx; end; pPackedPortion=^tPackedPortion; { Собственно Арифметический кодек  } tAriCodec=object private prFlags:tFlags; { Флаги режима работы кодека } protected prLastErrorCode:tError; prStatisticData:tAriStatistics; { данные статистики } prRangesData:tAriRanges; { данные статистики } prRangesDataDecode:tAriRangesForDecode; { данные статистики для декодирования } prLargeRange:tAriVeryLargeRange; {диапазон для осуществления кодирования } prCode:tAriVeryLargeCode; prTotalSymbolCount:tVeryLongCounter; prTotalByteCount:tVeryLongCounter; prTotalPortionCount:tVeryLongCounter; prMaxSymbolPerPortion:tFriquency; prMinSymbolPerPortion:tFriquency; private procedure ResetRegime; procedure SetErrorCode(aErrorCode:tError); public { Конструктор } constructor Init; { Деструктор } destructor Done; virtual; { Включение режима кодирования.} procedure EncodeReset; { Включение режима Декодирования.} procedure DecodeReset; procedure AlignStatistic(SetOn:boolean); overload; function AlignStatistic:boolean; overload; { Сброс текущего кода ошибки. Не влияет на работоспособность процедур ниже.} procedure ResetErrorCode; function CodecErrorCode:tError; { Подготовка кодирования буфера AInBuffer. Вычисляет статистику для буфера. И записывает заголовок буфера в aOutBuffer. } function StartEncodeBuffer( const aInBuffer; { буфер } aInBufSize:tBufferIndex; { размер буфера } var aOutBuffer; aOutBufSize:tByteBufferIndex; out aOutDataSize:tByteBufferIndex ):boolean; { кодирование буфера AInBuffer в AOutBuffer. При кодировании в AOutBuffer записываются только законченный код, неполный код остается в промежуточном буфере переноса. Оставшиеся данные будут записаны в AOutBuffer при следующем вызове Encode. !!!ПРИ ВЫЗОВЕ Encode с AInBufSize=0 происходит ПРИНУДИТЕЛЬНОЕ завершение кодирования порции данных и в AOutBuffer записывается признак завершения кодирования порции. } function Encode(const AInBuffer; { буфер со исходными данными } AInBufSize:tBufferIndex; { размер буфера с исходными данными } out AEncodedSize:tBufferIndex; { размер закодированной части, !!!может быть меньше AInBufSize, если все не влазит в AOutBuffer } var AOutBuffer; { кодированный буфер } AOutBufSize:tByteBufferIndex; { размер кодированного буфера } out AOutDataSize:tByteBufferIndex { размер кодированных данных в буфере } ):boolean; { Подготовка ДЕкодирования буфера AInBuffer. Считывается заголовок буфера. } function StartDecodeBuffer( const aCodedBuffer; aCodedBufSize:tByteBufferIndex; out aCodedBufSizeProcessed:tByteBufferIndex ):boolean; { декодирование буфера ACodedBuffer в AOutBuffer. При декодировании из ACodedBuffer считываются только полные порции кода. Недекодированный остаток запоминается в промежуточном буфере переноса и декодируется при последующем вызове. } function Decode(const ACodedBuffer; ACodedBufSize:tByteBufferIndex; out ADecodedSize:tByteBufferIndex; var AOutBuffer; AOutBufSize:tBufferIndex; out AOutDataSize:tBufferIndex):boolean; function PortionDecoded:boolean; { полное число обработанных символов НЕСЖАТОГО буфера} function TotalSymbolCount:tVeryLongCounter; { полное число обработанных байт СЖАТОГО буфера} function TotalCompressedByteCount:tVeryLongCounter; { полное число записей Арифметических кодов в СЖАТЫЙ буфер} function TotalPortionsCount:tVeryLongCounter; function MaxSymbolPerPortion:tFriquency; function MinSymbolPerPortion:tFriquency; { Степень сжатия } function CompressionRatio:double; end; IMPLEMENTATION constructor tAriCodec.Init; begin EncodeReset; end; destructor tAriCodec.Done; begin end; procedure tAriCodec.ResetRegime; begin prFlags:=prFlags-[fEncodeRegime, fDecodeRegime, fEncodeRegimeStarted, fDecodeRegimeStarted]; prLastErrorCode:=errOK; prTotalSymbolCount:=0; prTotalByteCount:=0; prTotalPortionCount:=0; prMaxSymbolPerPortion:=0; prMinSymbolPerPortion:=High(prMinSymbolPerPortion); end; procedure tAriCodec.EncodeReset; begin ResetRegime; { Инициируем БОЛЬШОЙ диапазон для кодирования} AriBase.InitLargeRange(prLargeRange); Include(prFlags,fEncodeRegime); end; procedure tAriCodec.DecodeReset; begin ResetRegime; prCode.NonDecodedSymbolCount:=0; Include(prFlags,fDecodeRegime); end; procedure tAriCodec.ResetErrorCode; begin prLastErrorCode:=errOK; end; procedure tAriCodec.SetErrorCode(aErrorCode:tError); begin prLastErrorCode:=aErrorCode; end; function tAriCodec.StartEncodeBuffer( const aInBuffer; aInBufSize:tBufferIndex; var aOutBuffer; aOutBufSize:tByteBufferIndex; out aOutDataSize:tByteBufferIndex ):boolean; var s:tSymbol; i:tSymbolCount; size:tByteBufferIndex; ShortStat:boolean; begin ResetErrorCode; aOutDataSize:=0; if not (fEncodeRegime in prFlags) then begin { НЕ режим кодирования } SetErrorCode(errNotInEncodeRegime); Result:=FALSE; Exit; end; if aInBufSize=0 then begin { НЕЧЕГО кодировать } SetErrorCode(errEncodeInBufferEmpty); Result:=FALSE; Exit; end; { Подсчитываем символы в буфере } AriBase.CountSymbols(aInBuffer, aInBufSize, prStatisticData); { Корректируем статистику - выравниваем на степень двойки } if AlignStatistic then AriBase.AlignStatistic(prStatisticData); { Инициируем диапазоны } i:=AriBase.CreateRanges(prStatisticData, prRangesData); if i=0 then begin { Нет данных статистики } SetErrorCode(errEncodeNoStatistic); Result:=FALSE; Exit; end; { Использовать укороченные данные статистики, если значение счетчиков влазит в WORD } ShortStat:=prRangesData.MaxCounter<=High(word); { Вычисляем размер данных статистики } if ShortStat then begin size:=SizeOf(tOutBufferHeader(aOutBuffer))-SizeOf(tOutBufferHeader(aOutBuffer).Statistics) +i*SizeOf(tOutBufferHeader(aOutBuffer).ShortStatistics[0]); end else begin size:=SizeOf(tOutBufferHeader(aOutBuffer))-SizeOf(tOutBufferHeader(aOutBuffer).Statistics) +i*SizeOf(tOutBufferHeader(aOutBuffer).Statistics[0]); end; if size>aOutBufSize then begin { НЕ влазим в буфер } SetErrorCode(errEncodeOutBufferTooSmallForHeader); Result:=FALSE; Exit; end; { Пишем заголовок буфера в aOutBuffer } with tOutBufferHeader(aOutBuffer) do begin Flags:=cVersion; If ShortStat then Include(Flags, bfUseShortStatistic); StatisticsLastElement:=i-1; end; { Пишем статистику в буфер aOutBuffer } i:=Low(i); if ShortStat then begin for s:=Low(s) to High(s) do begin if prRangesData.Ranges[s].Length>0 then begin tOutBufferHeader(aOutBuffer).ShortStatistics[i].Frequency:=prRangesData.Ranges[s].Length; tOutBufferHeader(aOutBuffer).ShortStatistics[i].Symbol:=s; Inc(i); end; end; end else begin for s:=Low(s) to High(s) do begin if prRangesData.Ranges[s].Length>0 then begin tOutBufferHeader(aOutBuffer).Statistics[i].Frequency:=prRangesData.Ranges[s].Length; tOutBufferHeader(aOutBuffer).Statistics[i].Symbol:=s; Inc(i); end; end; end; { копируем данные заголовка в буфер } aOutDataSize:=size; { Обновляем статистику } Inc(prTotalByteCount,size); { Все хорошо } Include(prFlags, fEncodeRegimeStarted); Result:=TRUE; end; function tAriCodec.Encode(const aInBuffer; aInBufSize:tBufferIndex; out aEncodedSize:tBufferIndex; var aOutBuffer; aOutBufSize:tByteBufferIndex; out aOutDataSize:tByteBufferIndex):boolean; procedure UpdateStatistic; begin if prMaxSymbolPerPortionprLargeRange.EncodedSymbolCount then prMinSymbolPerPortion:=prLargeRange.EncodedSymbolCount; end; var j:tByteBufferIndex; i:tBufferIndex; ppc:tByteBufferIndex; size:tByteBufferIndex; begin ResetErrorCode; aOutDataSize:=0; aEncodedSize:=0; if not (fEncodeRegimeStarted in prFlags) then begin { НЕ режим кодирования } SetErrorCode(errNotInEncodeRegime); Result:=FALSE; Exit; end; ppc:=0; i:=Low(i); j:=Low(j); Result:=TRUE; if aInBufSize=0 then begin { Завершение кодирования порции - выводим остатки } if prLargeRange.EncodedSymbolCount>0 then begin size:=SizeOf(tPackedPortion)-SizeOf(tVeryLongUInt) +(prLargeRange.Start.MostSignificantDigitIndex+1)*SizeOf(tDigit); if j+size>aOutBufSize then begin { НЕ влазим в буфер } SetErrorCode(errOutBufferTooSmallForPortion); Result:=FALSE; end else begin { НЕобновляем статистику кодирования - непоказательно } { UpdateStatistic; } { заносим данные кода в буфер } with pPackedPortion(@tByteBuffer(aOutBuffer)[j])^ do begin EncodedSymbolCount:=prLargeRange.EncodedSymbolCount; vlaAssignTillMSD(prLargeRange.Start, CodeData); end; j:=j+size; ppc:=ppc+1; { Инициируем БОЛЬШОЙ диапазон для кодирования } AriBase.InitLargeRange(prLargeRange); end; end; if Result then begin { Завершение кодирования порции - выводим КОНЕЦ БУФЕРА! } size:=SizeOf(tSymbolCount); if j+size>aOutBufSize then begin { НЕ влазим в буфер } SetErrorCode(errOutBufferTooSmallForPortion); Result:=FALSE; end else begin with pPackedPortion(@tByteBuffer(aOutBuffer)[j])^ do begin EncodedSymbolCount:=0; end; ppc:=ppc+1; j:=j+size; { останавливаем кодирование буфера } Exclude(prFlags, fEncodeRegimeStarted); end; end; end else begin { Кодируем } while Result and (iaOutBufSize then begin { НЕ влазим в буфер } SetErrorCode(errOutBufferTooSmallForPortion); Result:=FALSE; end else begin { копируем код в буфер } with pPackedPortion(@tByteBuffer(aOutBuffer)[j])^ do begin EncodedSymbolCount:=prLargeRange.EncodedSymbolCount; vlaAssignTillMSD(prLargeRange.Start, CodeData); end; Inc(j,size); Inc(ppc); { Инициируем БОЛЬШОЙ диапазон для нового кодирования} AriBase.InitLargeRange(prLargeRange); end; end; end; end; aEncodedSize:=i; aOutDataSize:=j; { Обновляем статистику } Inc(prTotalByteCount, j); Inc(prTotalSymbolCount, i); Inc(prTotalPortionCount, ppc); end; function tAriCodec.StartDecodeBuffer( const aCodedBuffer; aCodedBufSize:tByteBufferIndex; out aCodedBufSizeProcessed:tByteBufferIndex ):boolean; var s:tSymbol; size:tByteBufferIndex; begin aCodedBufSizeProcessed:=0; ResetErrorCode; if not (fDecodeRegime in prFlags) then begin { НЕ режим декодирования } SetErrorCode(errNotInDecodeRegime); Result:=FALSE; Exit; end; { Читаем заголовок буфера из aInBuffer } if (SizeOf(tOutBufferHeader)-SizeOf(tOutBufferHeader(nil^).Statistics))>aCodedBufSize then begin { НЕ влазим в буфер } SetErrorCode(errDecodeCodeBufferTooSmallForHeader); Result:=FALSE; Exit; end; with tOutBufferHeader(aCodedBuffer) do begin if Flags*cVersionMask<>cVersion then begin { НЕПРАВИЛЬНЫЙ буфер } SetErrorCode(errDecodeCodeBufferInvalid); Result:=FALSE; Exit; end; if bfUseShortStatistic in Flags then begin size:=(SizeOf(tOutBufferHeader)-SizeOf(Statistics)+(StatisticsLastElement+1)*SizeOf(ShortStatistics[0])); end else begin size:=(SizeOf(tOutBufferHeader)-SizeOf(Statistics)+(StatisticsLastElement+1)*SizeOf(Statistics[0])); end; if size>aCodedBufSize then begin { НЕ влазим в буфер } SetErrorCode(errDecodeCodeBufferTooSmallForHeaderStatistics); Result:=FALSE; Exit; end; aCodedBufSizeProcessed:=size; { обнуляем массив статистики } CountSymbols(NIL^,0,prStatisticData); { копируем статистику из заголовка буфера } if bfUseShortStatistic in Flags then begin for s:=Low(s) to StatisticsLastElement do begin prStatisticData[ShortStatistics[s].Symbol]:=ShortStatistics[s].Frequency; end; end else begin for s:=Low(s) to StatisticsLastElement do begin prStatisticData[Statistics[s].Symbol]:=Statistics[s].Frequency; end; end; end; { обновляем статистику кодирования } Inc(prTotalByteCount,size); { Инициируем диапазоны для декодирования } AriBase.CreateRanges(prStatisticData, prRangesDataDecode); Include(prFlags, fDecodeRegimeStarted); Result:=TRUE; end; ////////////////////////////////////////////////////////////////////////////////////// function tAriCodec.Decode( const aCodedBuffer; aCodedBufSize:tByteBufferIndex; out aDecodedSize:tByteBufferIndex; var aOutBuffer; aOutBufSize:tBufferIndex; out aOutDataSize:tBufferIndex ):boolean; var StopDecode:boolean; ppc:tVeryLongCounter; i:tByteBufferSize; j:tBufferSize; size:tByteBufferIndex; begin ResetErrorCode; if not (fDecodeRegimeStarted in prFlags) then begin { НЕ режим ДЕкодирования } SetErrorCode(errNotInDecodeRegime); Result:=FALSE; Exit; end; { Пытаемся декодировать} Result:=TRUE; i:=Low(i); j:=Low(j); ppc:=0; { Декодируем остатки прошлого вызова} { Декодирование остатка} while (j=aOutBufSize); while not StopDecode do begin { считываем заголовок порции } if aCodedBufSize<(i+SizeOf(tSymbolCount)) then begin { Не влазим в буфер } SetErrorCode(errDecodeCodeBufferTooSmallToReadPortionHeader); Result:=FALSE; StopDecode:=TRUE; end else begin with pPackedPortion(@tByteBuffer(aCodedBuffer)[i])^ do begin StopDecode:=(EncodedSymbolCount=0); if not StopDecode then begin if aCodedBufSize<(i+SizeOf(tSymbolCount)+SizeOf(tDigitIndex)) then begin { Не влазим в буфер } SetErrorCode(errDecodeCodeBufferTooSmallToReadPortionHeader); Result:=FALSE; StopDecode:=TRUE; end else begin size:=SizeOf(tPackedPortion)-SizeOf(CodeData.Uint) +(CodeData.MostSignificantDigitIndex+1)*SizeOf(CodeData.Uint.Digit0); if aCodedBufSize<(i+size) then begin { Не влазим в буфер } SetErrorCode(errDecodeCodeBufferTooSmallToReadPortion); Result:=FALSE; StopDecode:=TRUE; end else begin { считываем порцию кода } prCode.NonDecodedSymbolCount:=EncodedSymbolCount; vlaAssign(CodeData, prCode.Value); { Выводим код к верхней границе интервала, во избежание ошибок округления } vlaAdd(prCode.Value, tDoubleDigit(prRangesDataDecode.Total.SymbolCount-1)); { код считан } Inc(ppc,1); Inc(i,size); { Декодирование кода } while (j=aOutBufSize) end; end; end else begin Inc(ppc,1); Inc(i,SizeOf(tSymbolCount)); { останавливаем кодирование буфера } Exclude(prFlags, fDecodeRegimeStarted); end; end; end; end; { проверяем конец порции (буфера) } if Result and (prCode.NonDecodedSymbolCount=0) then begin if aCodedBufSize<(i+SizeOf(tSymbolCount)) then begin { Не влазим в буфер } end else if pPackedPortion(@tByteBuffer(aCodedBuffer)[i])^.EncodedSymbolCount=0 then begin Inc(i,SizeOf(tSymbolCount)); Inc(ppc,1); { останавливаем ДЕкодирование буфера } Exclude(prFlags, fDecodeRegimeStarted); end; end; { возвращаем размер декодированного } aOutDataSize:=j; { возвращаем размер декодированного } aDecodedSize:=i; { Обновляем статистику } Inc(prTotalByteCount, i); Inc(prTotalSymbolCount, j); Inc(prTotalPortionCount, ppc); end; function tAriCodec.TotalSymbolCount:tVeryLongCounter; begin Result:=prTotalSymbolCount; end; function tAriCodec.TotalCompressedByteCount:tVeryLongCounter; begin Result:=prTotalByteCount; end; function tAriCodec.TotalPortionsCount:tVeryLongCounter; begin Result:=prTotalPortionCount; end; function tAriCodec.CompressionRatio:double; begin CompressionRatio:=prTotalByteCount/(prTotalSymbolCount*SizeOf(tSymbol)); end; function tAriCodec.CodecErrorCode:tError; begin Result:=prLastErrorCode; end; function tAriCodec.PortionDecoded:boolean; begin Result:=(fDecodeRegime in prFlags) AND (not (fDecodeRegimeStarted in prFlags)); end; function tAriCodec.MaxSymbolPerPortion:tFriquency; begin Result:=prMaxSymbolPerPortion; end; function tAriCodec.MinSymbolPerPortion:tFriquency; begin Result:=prMinSymbolPerPortion; end; procedure tAriCodec.AlignStatistic(SetOn:boolean); begin if SetOn then Include(prFlags,fAlignStatistic) else Exclude(prFlags,fAlignStatistic); end; function tAriCodec.AlignStatistic:boolean; begin Result:=fAlignStatistic in prFlags; end; END.