スキップしてメイン コンテンツに移動

投稿

Initial run-length encoding@bzip2を読んでみた

Wikipediaのbzip2圧縮アルゴリズムの一部を読んだので意訳して紹介します。 参考にしたソースコードは bzip2-1.0.6 です。 Wikipedia https://en.wikipedia.org/wiki/Bzip2#Initial_run-length_encoding bzip2 ソースコード https://github.com/junkawa/bzip2/tree/master/bzip2-1.0.6 概要 bzip2では、入力データを読み込んだ時( copy_input_until_stop()@bzlib.c → ADD_CHAR_TO_BLOCK() → add_pair_to_block() ) に ランレングス符号化 を行う。 Wikipedia Any sequence of 4 to 255 consecutive duplicate symbols is replaced by the first four symbols and a repeat length between 0 and 251.   4〜255回、同じシンボルが連続した場合、「最初の4シンボル+残りの繰り返し回数」に置き換わる。 Thus the sequence "AAAAAAABBBBCCCD" is replaced with "AAAA\3BBBB\0CCCD", where "\3" and "\0" represent byte values 3 and 0 respectively.  "AAAAAAABBBBCCCD"は、"AAAA\3BBBB\0CCCD"に置き換わる。 AAAAAAA (Aが7回)は、最初の4シンボル(AAAA) + 残りの繰り返し回数(3)となる。 BBBB (Bが4回)は、最初の4シンボル(BBBB) + 残りの繰り返し回数(0)となる。 C,Dは連続回数が4回に達しないのでそのままとなる。 ここでは分かりやすさのため、A,B,Cというシンボルを使っているが、実際のbzip2では1シンボルは1バイト(0〜255の値)。 したがって、シンボル7...
コメントを投稿
続きを読む
最近の投稿

Zephyr build (7)

この記事で関係するターゲット linker.cmd ターゲット [zephyr_base]/Makefile linker.cmd: $(zephyr-deps) $(Q)$(CC) -x assembler-with-cpp -nostdinc -undef -E -P \ $(LDFLAG_LINKERCMD) $(LD_TOOLCHAIN) -I$(srctree)/include \ -I$(objtree)/include/generated $(EXTRA_LINKER_CMD_OPT) $(KBUILD_LDS) -o $@ $(zephyr-deps) TODO $(Q) [zephyr_base]/Makefile ifeq ("$(origin V)", "command line") KBUILD_VERBOSE = $(V) endif ifndef KBUILD_VERBOSE KBUILD_VERBOSE = 0 endif ifeq ($(KBUILD_VERBOSE),1) quiet = Q = else quiet=quiet_ Q = @ endif ... export quiet Q KBUILD_VERBOSE make V=1 などとすると、環境変数 Q は"" となる(or 未定義?)。それ以外では、Q は @ となる。 $(Q)$(CC) が gcc となる場合、実行する gcc ... というコマンドが表示されるが、@gcc となる場合、コマンドは表示されない。 5.2 Recipe Echoing 参照。 $(CC) 前の記事 参照。 $(LDFLAG_LINKERCMD) 未定義 $(LD_TOOLCHAIN) [zephyr_base]/Makefile LD_TOOLCHAIN ?= -D__GCC_LINKER_CMD__ LD_TOOLCHAIN が未定義の場合、-D__GCC_LINKER_CMD__ とする。 $(srctree) [zephyr_base]/Makefile ifeq ($(KBUILD_...
コメントを投稿
続きを読む

Zephyr build (6)

この記事で関係するターゲット 前の記事 参照 zephyr.lnk [zephyr_base]/Makefile -nostartfiles -nodefaultlibs -nostdlib -static -Wl,-X -Wl,-N -Wl,--gc-sections -Wl,--build-id=none -Wl,-Map=[zephyr_base]/samples/hello_world/microkernel/outdir/zephyr.map -L ./include/generated -u _OffsetAbsSyms -u _ConfigAbsSyms -e __start -Wl,--start-group -Wl,--whole-archive -Wl,--no-whole-archive drivers/built-in.o ./samples/hello_world/microkernel/src/built-in.o lib/built-in.o kernel/built-in.o misc/built-in.o net/built-in.o boards/built-in.o arch/built-in.o ext/built-in.o ./arch/x86/core/offsets/offsets.o -Wl,--end-group -L /Volumes/CrossToolNG/x-tools/i586-pc-elf/lib/gcc/i586-pc-elf/5.2.0/ -lgcc -nostartfiles 3.14 Options for Linking Do not use the standard system startup files when linking. The standard system libraries are used normally, unless -nostdlib or -nodefaultlibs is used. スタートアップファイル(crt*.oなど)をリンクしない。 -nodefaultlibs 3.14 Options for Linking Do not use the standard system ...
コメントを投稿
続きを読む

Zephyr build (5)

この記事で関係するターゲット 前の記事 参照 linker.cmd [zephyr_base]/samples/hello_world/microkernel/outdir/linker.cmd MEMORY { RAM (wx) : ORIGIN = 0x00100000, LENGTH = 192*1K IDT_LIST : ORIGIN = 2K, LENGTH = 2K } OUTPUT_FORMAT("elf32-i386", "elf32-i386", "elf32-i386") OUTPUT_ARCH(i386) SECTIONS { _image_rom_start = 0x00100000; _image_text_start = 0x00100000; text () : { *(.text_start) *(".text_start.*") *(.text) *(".text.*") *(.gnu.linkonce.t.*) *(.eh_frame) *(.init) *(.fini) *(.eini) } > RAM _image_text_end = .; devconfig () : { __devconfig_start = .; *(".devconfig.*") KEEP(*(SORT(".devconfig*"))) __devconfig_end = .; } > RAM gpio_compat () : { __gpio_compat_start = .; *(".gpio_compat.*") KEEP(*(SORT(".gpio_compat*"))) __gpio_compat_end = .; } > RAM rodata () : { *(.rodata) *(".rodata.*") *(.gnu.linkonce.r.*) . = ALIGN(8); _id...
コメントを投稿
続きを読む