Здравствуйте!

Имеется кучка файлов, которые можно поделить на две группы
1) длинные текстовые- например, лог 6 мегабайт ежедневно
2) куча коротких текстовых - например, ежедневно директория с 1440 файлами по 200 байт (ежеминутные данные)

Хочу их заархивировать с целью:
группа1 - чтобы уменьшить размер (важно при передаче)
группа2 - чтобы уменьшить количество файлов, просто склейка в один файл без сжатия уже подходит (то есть что-то типа tar уже достаточно) - важно для хранения.

Архивация происходит периодически и не в реальном времени- например, раз в сутки для уже собранных файлов. То есть изменять архив не нужно и скорость работы функции не важна, фоновая задача.
Обязательное требование- чтобы на компьютере это можно было разжать, используя доступные в интернете стандартные архиваторы, а не писать свой распаковщик. Я точно не буду применять архиватор в нестандартный архив.
И еще крайне желательно, чтобы задача не требовала больших объемов памяти (временных буферов) во время работы. При этом скорость работы практически не важна.


Вопрос: есть ли примеры решения таких задач? аппноты какие-нибудь, блоги, линки....
Обычно на МК решается обратная задача - разжать (прошивку, образ итд), да и то из нестандартного формата, а вот упаковщики в "стандартный" архив как-то не попадаются.

Ни и если кто-то может рассказать про личный опыт, что за архиватор применяли на МК, буду безмерно счастлив.

конкретно буду реализовывать на STM32F4, если это важно

есть же какой-то зип открытый, только возьми и скомпили

Тестировал кучку разных движков сжатия - https://geektimes.ru/post/264558/
Там среди прочего найдете проект под VisualStudio на PC. Можно экспериментировать с разными файлами насчет сжатия.
Но без ресурсов готовтесь к тому, что сжатие будет никакое.

опять же проблема, что хочу чтобы стандартные распаковщики мой файл понимали. Например, фраза вроде

Ну никак не говорит, так смогу я сжатое этой zlib разжать стандартным gzip или не смогу. И так практически везде. Такое ощущение, что подавляющее большинство делает "вещь в себе", под свой же распаковщик.

Про ресурсы- сколько-то килобайт под буфер могу найти (ну, может десяток). Да и файлы лежат рядом, могу доступаться к ним и перечитывать сколько угодно раз, без полного перемещения файла в RAM.


jszip ?

собственно, группа2 (много коротких файлов затарить в один, можно и без сжатия) интересует больше (задача с более высоким приоритетом). Может быть, это будут два разных метода и разные архиваторы, не обязательно все-в-одном.
A tar кто-то реализовывал на микроконтроллере?

minilzo
(__http://www.oberhumer.com/opensource/lzo/)

zip-ы, rar-ы, tar-ы и т.п. требуют для своей работы больших ресурсов, для микроконтроллера реально по затратам арифметическое сжатие.

Все эти алгоритмы параметрезированы. Распаковщики эту параметризацию понимают. Поэтому вы полностью управляете ресурсами. Любой засунете в пару десятков килобайт.
Дело только в том что сжатие такое дело, что чем меньше памяти под словари тем хуже сжатие.

Но TC скорее нужен не алгоритм сжатия, а формат контейнеров. Это другая тема.
Мои zip файлы компьютер понимает, но контейнер для многих файлов в одном zip-е я не делал.

Спасибо, буду думать (делать планирую буду ближе к новому году или даже после, чуть времени есть).
Все идет к тому что если хочу стандартный (zip какой-нить) то нужно больше усилий чем для нестандартного.
В принципе, наверное возможно и нестандарт, если разница в ресурсах велика....
в-общем-то оборудование небытовое, думаю смогу аргументировать применение и какого-нить небытового lzo.


Я в начале написал, у меня два разных случая в одном проекте
Для одного нужен сжиматель без контейнера, для другого- именно контейнер без сжимателя.

Причем прямо сейчас контейнер более востребован чем сжиматель. Неужто tar сложный формат, я почему-то думал что там не так все сложно.

А свой нестандартный последний сжиматель я еще в институте делал, по Хафману, на Z80 и ассемблере. Для курсовой сжимателя хватило, разжиматель пусть другие делают

tar это вообще элементарщина, был придуман чтобы потоково лить файлы на ленту.
Просто все привыкли что сейчас он еще заворачивается в gzip, вот и переживают...

Вообще по-хорошему надо найти исходники самого древнего unix - там будет и tar и gzip для минимальных ресурсов.

Глупости. На меге делал модем. Там было сжатие. Примерно 2 коэффициент. Сжатие в потоке даже с адаптивным словарём очень мало рерурсов ест. А распаковка - вообще 0. На CM3 даже не заметишь.
Существенный выигрыш получается при увеличении размера словаря и если словарь предопределён, до начала сжатия.

Да, я на это и надеялся, просто не открывал совсем, боялся испугаться
а как открыл, так просветлел сильно и сразу. может кому еще пригодится, тут ссылки оставлю:
этого и этого, по-моему, вполне хватит для написания своего тара.

ну и просто обсуждение : тут и тут про тар "на пальцах на русском"

В-общем, спасибо огромное, с контейнером все понятно, красиво и просто, и непонятно что тут "ресурсами" называть
а это была более срочная часть роботы, чем сжиматель, так что вдвойне приятно.- сделаю это, а сжиматель потом, он не так приоритетен

Осталось понять что со сжимателем делать, но теперь это совсем не срочно.


Что именно использовали на Меге, какой упаковщик?

у меня файл завершен и записан на диск, и времени много. Могу хоть 10 раз его перечитать если это для составления и корректировки полного словаря нужно. Но вот RAM хотелось бы экономить.
Адаптивный словарь меня скорее всего тоже устроит. Текст, причем только нижняя половина ASCII, много похожих строк. То есть по малой части текста можно очень неплохо подходящий всему тексту словарь сделать. Zip эти 6 мегабайт жмет в 10 раз (на минимальной степени сжатия, 1), на максимальной (9) - в 15 раз жмет.

Самая дурь, это называть какие-либо конкретные коэффициенты сжатия.
Хотите подкину файл который после вашего сжатия не уменьшится, а увеличится в объеме?

Речь шла о текстовом документе.
Скажем так. Пробовал пересжимать его зипом Особо выигрыша не было.
По сути алгоритм не изменился. Ничего нового не выдумали. Я уже писал. Играет роль размер словаря (особенно на крупных файлах) и предустановленный словарь. Причём словарь можно сделать наиболее употребляемый в данном случае. Это даст существенный выигрыш.
Как вариант взять и пропустить тексты через архиватор с стандартным словарём. После чего выделить получившийся закинуть на обе стороны.
В любом случае само сжатие/ распаковка используют мало ресурсов. Не в пример крипто. Только память. Памяти по нынешним временам 64к - не о чём.

"Имя, сестра, имя!"

Я писал свой алгоритм для модема. Но все архиваторы построены в основе своей на https://ru.wikipedia.org/wiki/Алгоритм_Лемп..._—_Зива_—_Велча.
То есть ZIP, на сколько я понимаю.
ЗЫ: Прошу прощения, посмотрел, оказывается я не прав. Буква Z ввела в заблуждение. Ну и когда RAR смотришь - там про словарь тоже указывается. Короче я использовал модифицированный метод словаря. Который в модемах применяется. Там словарь передаётся прямо в потоке. И параллельно формируется на обоих концах. Сжатый файл таким методом, сжимается ZIPом совсем не значительно.

"The gzip sources, written in C, are available here in various formats".

Посмотрите на https://github.com/atomicobject/heatshrink
Это куда больше подходит для МК, чем gzip.

В моей статье есть сравнение LZSS (на котором построен heatshrink) и Zlib
LZSS хуже сжал.
Но памяти при этом потребовал не намного меньше чем Zlib.
Разжимет он опять же медленней чем Zlib.
Хотя есть и достоинства.
Но самое интересное, что оба юзают malloc. Т.е. расход памяти у них не детерерминирован со всеми вытекающими.

Хм. Или никто не знает, или посчитали несущественным.
В tar минимальный занимаемый размер это 512 байт на заголовок плюс 512 байт на файл, то есть минимум 1 килобайт на файл. Несколько расточительно для файлов в 200 байт. Хотя даже в лучшем случае (у меня это 2КБ размер кластера) уже дает выигрыш вдвое. А в случае дефолтового формата "с завода" с его 32 К на кластер- уже ого-го!

Хотя наверное все-таки для этой части задачи прямо сейчас- tar. Уж все остальное точно сложнее будет сделать чем его. Да и простое дописывание файлов в уже имеющийся архив - это для меня плюс, я это буду использовать и за счет этого сниму ряд других проблем.

Интересно, нет ли в каком-то zip или еще где опции "просто сохранить файлы вместе без сжатия"? Может, в этом случае можно более рационально сделать по размеру (зип-файл, но не сжатый а просто склеенные внутри по правилам зипа файлы)

Upd:
посмотрел первоисточник - такое ощущение что можно и просто навпихивать несжатое в zip. Заголовок выглядит компактным, и опять же работы ненамного больше по сравнению с tar. По крайней мере, в 2 часа ночи мне так кажется...

Не могу согласиться, malloc как раз необязателен, т.к. есть макрос HEATSHRINK_DYNAMIC_ALLOC определяющий его использование. Это большой плюс. Что касается сжатия, то это упрощенная ради облегчения версия и ждать от нее чудес сжатия по-моему нет смысла. Но она намного лучше еще более легкого RLE.

Архиватору требуется большой объем памяти для анализа инф-ии.
Если у Вас логи "типовые", то для создания словаря для паковки можно их (логи) слить
на PC, и получить "словарь", который потом прошить в контроллер.
Т.о. в контроллере будет не поный архиватор, а его урезанная часть,
с примитивным анализом - только на цепочки повторяющихся символов.
и упаковку "словарных" комбинаций.

Про контейнер- альтернативу использованию тара.
Как просто контейнер- ZIP формат без сжатия выглядит гораздо приятней (заголовок короче и файл занимает столько сколько занимает). В минусах что нужно обязательно CRC32 считать и (вроде бы обязательно) перепаковывать при добавке нового файла.
И еще документирован формат прекрасно- одного того "APPNOTE.TXT - .ZIP File Format Specification", на который я давал ссылку, достаточно для написания своего "упаковщика с уровнем сжатия 0".

Такое ощущение, что для меня писали, все ответы прямо в спецификации есть.

кто-то развлекался? где незамеченные мной подводные камни?

вот тут еще красивей нарисовано что к чему, отличное дополнение у чисто текстовому описанию основной спецификации.
Сейчас поигрался- получается что зип-контейнер (без компрессии) на 10 файлов по 175 байт занимает 3854 байта, это почти в 3 раза меньше чем длина тара для них же (10752 байта).

Ещё ISO есть.

10 * 175 = 1750. "Выигрыш" ... неочевиден.
Может, лучше придумать свой компактный формат логов? Типа, не писать нули подряд, записывать дельту, и т.п.

ViKo, Вы что имеете в виду? Я не понял что с чем Вы сравнили. 10 файлов без контейнера занимает не 1750 байт, а 10 кластеров на диске (в лучшем случае- 20 килобайт, в худшем/стандартном - 320 килобайт)


Не, спасибо, это не буду. Тут психологический барьер: tar и zip для контейнера это нормально, а iso - это для другого

В вашем устройстве с микроконтроллером есть диск (с кластерами)? Или вы хотите место на компьютере, куда передаете, сэкономить? Тогда там и сжимайте, на компьютере.
Вам обязательно накапливать ежеминутные данные в виде отдельного файла? Складывайте в ежечасные.

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

Да, у меня есть кластеры (в виде файловой системы). На компьютере сэкономить место - не первостепенная задача, но там тоже проблема есть, если не архивировать (inode table совсем не резиновая). Нет, это не для передачи архив, это резервное хранилище на случай оффлайновой работы и разборок в случае проблем. А передаются данные пофайлово в онлайне, так же и обрабатываются, ежеминутно. но в хранилке локальной остается копия, которая должна совпадать с переданным оригиналом.

Вы, вероятно, не сталкивались с подобным, у меня сейчас ситуация следующая: за 100 дней накапливается почти полтора миллиона файлов, занимающие 4 гигабайта (если кластер 32к) на устройстве хранения, при этом собственно файлы имеют общий объем 24 мегабайта.

Понятно. Если это резервный архив, то почему не делать один файл на час или день? А на компе своей утилиткой выделять ежеминутные данные, когда это в исключительном случае потребуется. Зачем эта 100% идентичность? Тем более, все равно объединяете в один файл. Вам, конечно, виднее.
Еще и на количестве записей на диск сэкономите.

Что-то очень сомнительно. При таком количестве файлов время доступа к файлу на создание-запись должно быть в пределах десятков секунд.
С такими тормозами я не представляю чем дивайс еще может заниматься.

Ну так они не внавал миллионами лежат, а по дневным дирректориям, в каждой 1440 файликов. В момент копирования нового файла "в архив" тормозов сильных нет, всего-то 1237-й файл в известную дирректорию добавить.
Тормоза только после включения и ежесуточно, когда система проверяет все архивные фолдеры на предмет "а кто тут старее чем указанное в конфиге время жизни для этого типа файлов?" и удаляет старые. Вот это да, закат солнца вручную. (кстати, мой контейнер и этому горю поможет). Но это одна из задач многозадачки, так что не критично -остальное бегает в параллель.

А что сомнительно? я не вижу слабых мест при использовании FAT в виде иерархической структуры: большого числа файлов, распиханного по дирректориям.
Вот в Линуксе с его единой таблицей inode есть потенциальные грабли насчет количества файлов. Но там скрипты подтирают- принятый файл сразу после затягивания в базу данных добавляется в архив и удаляется. Как-то слетел скрипт - так inode на FTP была забита за неделю

Я с Вами полностью согласен, так нужно делать, когда это возможно. Но сильно не хочется свою утилитку делать (не только из-за лени). А еще больше "попонтоваться" хочется: "ну что, конкуренты коллеги, у меня zip, а у вас?"

Для подобных задач уже надо использовать пром. компьютер с "настоящей" осью, в которой уже все упаковщики работают "из коробки", а если инфа еще и важная, то есть смысл и raid прикрутить или в базы данных скидывать...

Перепроверил: у ISO большой заголовок на диск, и он хранится в теле этого iso файла. Плюс минимальный размер сектора - 2 килобайта, и каждый файл в своем секторе. В результате стоимость входа 50 килобайт, плюс по 2 килобайта на файл.
В-общем, это как переход от одной операционки к другой, выигрыша по занимаемому месту нет никакого так как нужно хранить файловые таблицы и файлы квантуются сектором 2К.

Пока что zip видится лучшим контейнером. попробую накропать что-то за вечерок... CRC32 не нравится, да и промежуточный буфер(даже файл) нужен для хранения этих хвостовых central directory header, но нет в мире совершенства....

В-общем, реализовал tar с дописыванием в архив новых файлов по нужде. Имею желание в будущем добавить gzip и получить tgz.

сам по себе zip - тупик, если нужно даже сжать много файлов. Как контейнер он лучше чем tar, а дальше сплошные минусы и по сложности подготовки(нужно много данных хранить даже просто для организации контейнера,) и в будущем сжатия большого не даст. А делать zip для контейнера и потом еще раз сжимать этот зип как один файл- это мазохизм, уж лучше стандартный путь, через тар. Ну и с таром дописывание- это норма, а не изврат как с зипом.

Кстати, с Таром тоже хватило эротики- описание только на первый взгляд понятное, пришлось и в исходники за деталями залезть, а они не самые простые. Первые(простые)- не годятся, так как формат поменяли по дороге, по этой же причине в интернете разброд и шатание, могу найти противоречащие друг другу описания.
Более того- разные программы дают разный файл, и по хедеру и по длине, например ТоталКомандер и 7-zip, но не отказываются раскодировать файлы друг друга- видна повышенная толерантность и пофигизм к содержимому неосновных полей хедера и финальному маркеру (7Zip- лучше, я не нашел отклонений от описания в полученном с его помощью файле).

следующий виток- gzip, но тут вроде есть готовое, хочу попробовать mini_gzip

Я применила для такой задачи (сбор и ежесуточное архивирование данных) х86-совместимый пром.компьютер под Linux.
Для задачи попроще (файл был один) на STM32F103 применила архивaтор XZ Embedded

Так мне и надо было распаковать 1 файл на МК.
Если надо упаковать, есть библиотеки:
1. miniz
2. liblzf

Похоже ничего нового в этом мире нет.
Перепевки все тех же алгоритмов предложеных в начале темы.
Но по условиям темы вы должны еще показать достаточно распространенный разархиватор на PC для указанных форматов.

miniz пишет ZIP файлы.

При компиляции релиза liblzf получается (рас/у)паковщик в виде бинарника lzf которым элементарно просто пользоваться.

Может быть использовать не архиватор, а файловую систему со сжатием, например NTFS?
Исходники ntfs-3g бесплатны, открыты. А за деньги можно приобрести NTFS Embedded

Да можно много барахла найти по всяким свалкам исходников, никто не спорит.
Но во первых вы даже видимо не смотрели сколько памяти требует этот miniz, а во вторых видимо думает, что в STM32 есть такая же файловая система как в линуксе.

Не только барахла, много ценного тоже нарыть можно.
На STM32 можно работать и с файловой системой как в Линуксе, и с самим Линуксом!

Спасибо, но на линукс ради архиватора переходить не стану в данном устройстве.
У меня этот архиватор- задача опциональная, так что революцию в архитектуре не планирую, причин нет. Вот tar был необходим, это да, но он красиво лег и на то что уже есть.
Я поскреб по сусекам- наскреб у себя около полмегабайта РАМа, который смогу архиватору "во временное пользование" выделять, думаю это сильно расширит горизонты. Но вот нерезиновое ПЗУ экономить все равно нужно.

И, к слову, называль Линуксом uClinux - ну, у меня лично язык не поворачивается. Все ж таки MMU нужно, чтоб Линуксом назваться. И я с uClinux наигнался в его Блекфиновской инкарнации, и драйверы свои писал в него к моему железу тогдашнему, и оно даже работало. Как-то работало. Очень "как-то". И то был Блэкфин, а не свистелка STM32.

Вопрос к ТС-у:
Как я понял Вы остановились на tar? И уже имплементировали его?
У меня сейчас в чём-то сходная задача: нужно в прошивку устройства добавить содержимое некоего HTTP-сервера. И я тоже искал контейнер, чтобы объединить все файлы в один файл, из которого уже можно находить нужные отдельные файлики внутри firmware. Вопрос о сжатии пока не стоит.
Я посмотрел на tar, но мне показалось, что у него большой оверхед на всякие заголовки и т.п.
И я остановился на cpio. Вы его рассматривали? https://habrahabr.ru/post/130092/
Утилитка для него есть и под винду.

Да, сейчас я использую tar.
Нет, я не рассматривал cpio, так как не думал о нем как о "стандартном" упаковщике.
Очень может быть, что cpio лучше. По оверхеду он явно лучше, но может есть какие-то хитрости.