クワイン・マクラスキー法とペトリック法による論理圧縮
qmc.hを修正
qmc_main.c : 246
if(out_count==0) break ;
追加
qmc_main.c : 766～
３行追加
概要
「クワイン・マクラスキー法とペトリック法による論理圧縮アルゴリズムをCで実装」
http://qiita.com/jun6231jp/items/41b492ce31a109e4cec6
のソースを改造しました。
改造点は
オンメモリで動作するように
ロジックを整理して高速化
複数出力に対応
などです。
ビルド
make
all : qmc mask12.h
.PHONY : all
mask12.h : mask12.c
gcc mask12.c -o mask12
./mask12 > mask12.h
qmc : qmc_main.c qmc.h qmc_misc.c qmc_misc.h readfile.c readfile.h mask12.h
gcc qmc_main.c qmc_misc.c readfile.c -o qmc -Wall -O3 -std=c99
使い方
qmc filename
入力ファイルは
０個以上のスペース又はタブのあと １こ以上の '0' か '1'
そのあと１こ以上のスペース又はタブのあと １こ以上の '0' か '1
それ以外の文字が出てきたら無視。
入力の無い行は無視します。
7seg.tblを参考にしてください。
入力は12ビットまで対応していますが、チェックはしていません。
出力は
Ab + aB [CR] ABC + abc
の様になります。
小文字は大文字の否定です。
この出力は
(A & !B) | (!A & B) | (A & B & C) | (!A & !B & !C)
という意味です。
オプション
-r 必要最小限のビットを求める処理をしません。
-f 出力フォーマットをオリジナルに合わせます。つまり [0] + [`1][2] のような表示です。
デフォルトでは ABC + abc の様になります。
-m 計算途中のメッセージを出力します。
-s 計算に先立って、入力をソートし重複行を削除します。
テーブル作成
必要最小限のビットを求める時、nビット立った数値をnの小さい順、数値の小さい順に調べるのですが、これのデータは実行時に作ると時間がかかります。
そこで先に計算してテーブルを作ります。
１２ビットまで対応なので、テーブルサイズは4Kになります。
mask12.cがそのツールです。
ソース
qmc.h
#ifndef _QMC_H_
#define _QMC_H_
#define LOGIC_MAX_BITS 12 // 入力bit最大長
#define LOGIC_MASK 0xfff // ロジック部分を取り出すマスク
#define OUT_MASK_SHIFT 16
#define OUT_MASK (1UL << (OUT_MASK_SHIFT))
#define MASK_TABLE_SIZE (1UL << (LOGIC_MAX_BITS))
#define LT_INDEX_NOT_USE 0
#define LT_INDEX_IN 1
#define LT_INDEX_UT_BASE 0x80
#define LT_INDEX_MASKED 2
#define LT_INDEX_TEMP_BASE 0x100
#define LT_INDEX_ 0x8000
#endif
qmc_misc.h
#ifndef _LCP_MISC_H
#define _LCP_MISC_H
#include "readfile.h"
typedef struct tagLogicTable{
int index ; // 0:未使用 1:入力テーブル 0x100～ 圧縮テーブル
int bits ; // データのビット数
int pieces ; // 一行のデータ数 １行目追加中のみ増加する
int lines ; // 行数
int t_line ; // 追加中の行
int t_pos ; // 行のはしっこ
uint32_t** logic ; // データ
uint32_t* logic_buff ; // メモリブロックの先頭
int buff_lines ; // 確保済み行数
int buff_len ; // 確保済み要素数
} LogicTable ;
// 計算一回分のデータ
typedef struct tagInTable{
int nline ;
int logic_bits ; // 入力部分のビット数
uint32_t* logic_arg ;
char * out_arg ;
uint32_t rebuild_mask ; // リビルド済み
int nline_rebuild ;
int bits ;
uint32_t* logic ;
char * out ;
} InTable ;
LogicTable *lt_search(int index) ;
int lt_setup(void) ;
LogicTable* lt_make(int index) ;
int lt_delete(int index) ;
int lt_rename(int old_index, int new_index) ;
int lt_newline(int index) ;
void lt_setbits(int index, int bits) ;
int lt_add_piece(int index, uint32_t piece) ;
void lt_freeall(void);
void free_in_table(InTable* in_table);
void setup_in_table(InFile* in_file, InTable* in_table, int clmn);
int huming_weight16(uint32_t a);
int msb16(uint32_t v) ;
int trim_CRLF(char *str) ;
#endif
readfile.h
#ifndef _READFILE_H_
#define _READFILE_H_
// 入力ファイル 正規化済み
typedef struct tagInFile{
int nline ; // 入力データ行数
int logic_bits ; // 入力部分のビット数
uint32_t* logic ;
int out_bits ; // 出力の桁数
char ** out ;
} InFile ;
int read_in_file(InFile* in_file, char* filename);
#endif
qmc_main.c
/*
クワイン・マクラスキー法とペトリック法による論理圧縮
参照
http://qiita.com/jun6231jp/items/41b492ce31a109e4cec6#%E3%82%BD%E3%83%BC%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89
*/
#include <assert.h>
// #define NODEBUG
#include <unistd.h>
#include <stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include "qmc.h"
#include "qmc_misc.h"
#include "readfile.h"
#include "mask12.h"
int msg_out=0 ; // 各処理でのメッセージ出力
int org_format=0 ; // 出力フォーマットをオリジナルに合わせる
int remake=1 ; // 最小入力ビットを計算する
int sort_table=0; // 入力テーブルをソートする（元のプログラムと結果を比較するためにディセーブルにしてある）
int read_opt(int argc, char* argv[]){
int i ;
int in_file=-1 ;
for(i=1 ; i<argc ; i++){
if(argv[i][0]=='-'){
switch(argv[i][1]){
case 'm': msg_out=1 ; break ;
case 'f': org_format=1 ; break ;
case 'r': remake=0 ; break ;
case 's': sort_table=1 ; break ;
}
}
else if(argv[i][0]!=0){
in_file=i ;
}
}
return in_file ;
}
int cmp_int(const void *left, const void *right)
{
return *(int *) left - *(int *) right;
}
int cmp_short(const void *left, const void *right)
{
return *(short *) left - *(short *) right;
}
static int cmpsize;
int cmp_mem(const void *left, const void *right)
{
int i ;
int cmp=0 ;
uint32_t *l=*(uint32_t**)left ;
uint32_t *r=*(uint32_t**)right ;
for(i=0 ; i<cmpsize ; i++, l++, r++){
if(*l < *r){
cmp=-1 ;
break ;
}
else if(*l > *r){
cmp=1 ;
break ;
}
}
return cmp ;
}
// logic をソートし、重複する行を削除する
int sort_and_uniq(uint32_t *logic, int logic_line)
{
qsort(logic, logic_line, sizeof(uint32_t), cmp_short);
int count = 0;
for (int i = 1 ; i < logic_line; i++) {
if ((logic[count] & LOGIC_MASK) != (logic[i] & LOGIC_MASK)) {
logic[++count] = logic[i];
}
}
return ++count ;
}
int uniq(int index)
{
uint32_t **ubuff = NULL;
int i, j;
int line_count = 0;
LogicTable* tbl_in=lt_search(index) ;
line_count=tbl_in->lines ;
cmpsize=tbl_in->pieces ;
ubuff=tbl_in->logic ;
for (j = 0; j < line_count; j++) {
qsort(ubuff[j], cmpsize, sizeof(uint32_t), cmp_int);
}
qsort(ubuff, line_count, sizeof(uint32_t *), cmp_mem);
int item_count = 0;
for (i = 1; i < line_count; i++) {
if (memcmp(ubuff[item_count], ubuff[i], cmpsize * sizeof(int)) != 0) {
item_count++;
ubuff[item_count] = ubuff[i];
}
}
tbl_in->t_line=item_count ;
item_count++;
tbl_in->lines=item_count ;
if(msg_out){printf(" uniq(%d) ", item_count); fflush(stdout) ;}
if (item_count > 1) {
return 2;
}
return item_count;
}
// 入力から１段階の圧縮
int logic_compress_2(int index)
{
LogicTable* tbl_in ;
int clen;
int i, j, k, m;
int groupchk = 0;
int count = 0;
int count2 = 0;
int res;
int pattern ;
int pattern_n ;
int tbl1=LT_INDEX_TEMP_BASE+1 ;
int tbl2=LT_INDEX_TEMP_BASE+2 ;
lt_delete(tbl1);
lt_delete(tbl2);
lt_make(tbl1);
lt_make(tbl2);
tbl_in=lt_search(index) ;
assert(tbl_in!=NULL) ;
clen=tbl_in->bits ;
lt_setbits(tbl1, clen) ;
lt_setbits(tbl2, clen) ;
int in_count = tbl_in->pieces ;
int out_count = in_count ;
uint32_t* logic=tbl_in->logic[0] ;
uint32_t* logic_temp = malloc(in_count*sizeof(uint32_t)) ;
memcpy(logic_temp, tbl_in->logic[0], in_count*sizeof(uint32_t)) ;
uint32_t* logic_out = tbl_in->logic[1] ;
for (i = 0; i < in_count; i++) {
int dist ;
pattern=logic_temp[0] ;
for (j = 0; j < in_count; j++) {
if(logic[j]==pattern){
break;
}
}
if(j==in_count || (logic_out[j] & OUT_MASK)){
// ビット反転と挿入比較ループ
for (m = 0; m < clen; m++) {
int mask=1UL << (clen-m-1) ;
pattern_n=(pattern & ~mask) | ((~pattern) & mask) ;
for (k = 0; k < in_count; k++) {
if (logic[k]==pattern_n) {
break;
}
}
if(k==in_count || (logic_out[k] & OUT_MASK)){ // 元データと一致しないか、一致して出力が１
groupchk = 1;
lt_add_piece(tbl2, pattern) ;
lt_add_piece(tbl2, pattern_n) ;
lt_newline(tbl2) ;
count2++;
for (k = 0, dist = 0; k < out_count; k++) { // patternかpattern_nと一致するのを削除
if (logic_temp[k]!= pattern && logic_temp[k]!=pattern_n) {
logic_temp[dist] = logic_temp[k];
dist++;
}
}
out_count = dist;
}
}
if (groupchk == 0) {
lt_add_piece(tbl1, pattern) ;
lt_newline(tbl1) ;
count++;
for (k = 0, dist = 0; k < out_count; k++) {
if (logic_temp[k]!=pattern) {
logic_temp[dist] = logic_temp[k];
dist++;
}
}
out_count = dist;
}
groupchk = 0;
}
else { // 一致して出力が０
for (k = 0, dist = 0; k < out_count; k++) {
if (logic_temp[k]!=pattern) {
logic_temp[dist] = logic_temp[k];
dist++;
}
}
out_count = dist;
}
if(out_count==0) break ;
}
if (count > 1) {
if(msg_out){printf("logic comp 1 ... end %d lines\n", count);}
}
if (count2 > 1) {
res = uniq(tbl2);
if(msg_out){printf("logic comp 2 ... end %d lines \n", count2);}
}
else {
res = 0;
}
free(logic_temp) ;
return res;
}
int logic_compress_n(int half)
{
LogicTable* tbl_in ;
int tbl1=LT_INDEX_TEMP_BASE+half ;
int tbl2=LT_INDEX_TEMP_BASE+half*2 ;
int l, i, m;
int ret=0 ;
int bit_pos ;
int count = 0;
int count2 = 0;
int countpast = 0;
int org_flag = 0;
if(msg_out){printf("comp N(%d) start ", half); fflush(stdout);}
lt_make(tbl2) ;
tbl_in=lt_search(tbl1) ;
int nline=tbl_in->lines ;
int part_len=tbl_in->bits ;
uint32_t *pattern_n=malloc(half*sizeof(int)) ;
LogicTable *tbl_master=lt_search(LT_INDEX_IN) ;
lt_setbits(tbl2, tbl_master->bits) ;
int master_ndata = tbl_master->pieces ;
uint32_t* logic=tbl_master->logic[0] ;
uint32_t* logic_out = malloc(sizeof(uint32_t) * master_ndata) ;
for(i=0 ; i<master_ndata ; i++){
logic_out[i] = (tbl_master->logic[1][i] & OUT_MASK) >>OUT_MASK_SHIFT ;
}
for(i=0 ; i<nline ; i++){
// カラム位置ループが外側なのは、カラム位置によってまとめるため。
for (bit_pos = 0; bit_pos < part_len; bit_pos++) { // 各桁について（ハミング距離を計算するので、桁位置ループが外）
uint32_t *pattern=tbl_in->logic[i] ;
count = 0;
org_flag = 0;
//
int mask=1UL << (part_len-bit_pos-1) ;
for (l = 0; l < half; l++) { // bit-k の違うものを探す
if((pattern[0] & mask) != (pattern[l] & mask))
break;
}
if (l != half) // 見つかった
continue ;
for (l = 0; l < half; l++) {
pattern_n[l]=(pattern[l] & ~mask) | ((~pattern[l]) & mask) ;
countpast = count;
for (m = 0; m < master_ndata; m++) {
if(logic[m]==pattern_n[l]){
if (logic_out[m] == 1) {
count++;
break;
}
else { // 出力0
org_flag++;
break;
}
}
}
if (org_flag == 0 && countpast == count) // Don't care
count++;
}
// ハミング距離１のパターン書き出し
if (count == half) {
for (int n = 0; n < half; n++) {
lt_add_piece(tbl2, pattern[n]) ;
lt_add_piece(tbl2, pattern_n[n]) ;
}
lt_newline(tbl2) ;
count2++;
}
}
}
if (count2 > 1)
ret = uniq(tbl2);
if(msg_out){printf(" ... end \n"); fflush(stdout);}
free(logic_out) ;
free(pattern_n);
return ret;
}
int resize(int half)
{
int i, j, n, m;
uint32_t *i_part; // part[N]を整数に変換した配列
uint32_t **fp2_i_buff; //
int i_buff_len = 0; // 各行の要素数
int line_num = 0;
int count = 0;
int count2 = 0;
int br = 0;
int tbl1=LT_INDEX_TEMP_BASE+half ;
int tbl2=LT_INDEX_TEMP_BASE+half*2 ;
int tbl_t=LT_INDEX_UT_BASE ;
clock_t start, end;
LogicTable *tbl_in1 ;
LogicTable *tbl_in2 ;
lt_make(tbl_t) ;
tbl_in1=lt_search(tbl1) ;
tbl_in2=lt_search(tbl2) ;
lt_setbits(tbl_t, tbl_in1->bits) ;
line_num=tbl_in2->lines ;
i_buff_len=tbl_in2->pieces ;
fp2_i_buff=tbl_in2->logic ;
if(msg_out){printf(" start resize(%d) ", half); fflush(stdout);}
start = clock();
int tbl1_line=tbl_in1->lines ;
count=tbl_in1->pieces ;
for(m=0 ; m < tbl1_line ; m++){
i_part=tbl_in1->logic[m] ;
count2 = 0;
for (i = 0; i < line_num; i++) {
uint32_t *wpos;
wpos=fp2_i_buff[i] ;
for (br = 0, j = 0; j < count; j++) {
uint32_t *pos = wpos;
for (n = 0; n < i_buff_len; n++, pos++) {
if (i_part[j] == *pos) {
br++;
break;
}
}
if (n == i_buff_len) break; // 同じものが見つからなかった
}
if (br != count) count2++;
else break;
}
if (count2 == line_num){
for (n = 0; n < count; n++) {
lt_add_piece(tbl_t, i_part[n]) ;
}
lt_newline(tbl_t) ;
}
}
lt_delete(tbl1) ;
lt_rename(tbl_t, tbl1) ;
tbl_in1=lt_search(tbl1) ;
end = clock();
if(msg_out){
printf("exec time %f ", (end - start) / 1000.0);
printf(" ..end table_%d : %d lines \n", half, tbl_in1->lines); fflush(stdout);
}
count=lt_search(tbl1)->lines ;
return count ;
}
void remove_dup(int dim)
{
int i, l, m, n ;
if(msg_out){printf("removing duplication(%d) ...", dim); fflush(stdout);}
clock_t start, end;
start = clock();
int tbl_temp=LT_INDEX_UT_BASE ; // compact_temp
lt_make(tbl_temp) ;
int tbl_slist=LT_INDEX_UT_BASE+1 ; // search_list
lt_make(tbl_slist) ;
int tbl1=LT_INDEX_TEMP_BASE+dim ;
int tbl2=LT_INDEX_TEMP_BASE+dim*2 ;
int tbl_master=LT_INDEX_IN ;
LogicTable *tbl_in=lt_search(tbl1) ;
int line_count=tbl_in->lines ;
int count = tbl_in->pieces ;
lt_setbits(tbl_temp, tbl_in->bits) ;
int *br = malloc(count*sizeof(int));
uint32_t *line2 ;
for(i=0 ; i<line_count ; i++){
LogicTable *ptr ;
int search_count ;
uint32_t *part ;
int charnum ;
memset(br, 0, sizeof(int) * count);
tbl_in=lt_search(tbl1) ;
part=tbl_in->logic[i] ;
//同位ファイルからパターン検索
ptr=lt_search(tbl1) ;
search_count=ptr->lines ;
charnum=ptr->pieces ;
for(m=0 ; m<search_count ; m++){
line2=ptr->logic[m] ;
for (n = 0; n < count; n++) {
for(l=0 ; l<charnum ; l++){
if (line2[l]==part[n]) {
br[n]++;
break;
}
}
}
}
//上位ファイルからパターン検索
ptr=lt_search(tbl2) ;
search_count=ptr->lines ;
charnum=ptr->pieces ;
for(m=0 ; m<search_count ; m++){
line2=ptr->logic[m] ;
for (n = 0; n < count; n++) {
for(l=0 ; l<charnum ; l++){
if (line2[l]==part[n]) {
br[n]++;
break;
}
}
}
}
ptr=lt_search(tbl_slist) ;
search_count=ptr->lines ;
charnum=ptr->pieces ;
for(m=0 ; m<search_count ; m++){
line2=ptr->logic[m] ;
for (n = 0; n < count; n++) {
for(l=0 ; l<charnum ; l++){
if (line2[l]==part[n]) {
br[n]--;
break ;
}
}
}
}
//真理値表からパターン検索
ptr=lt_search(tbl_master) ;
search_count=ptr->pieces ;
line2=ptr->logic[0] ;
for(m=0 ; m<count ; m++){
for (n = 0; n < search_count; n++) {
if (line2[n]==part[m])
break;
}
if (n == search_count)
br[m] = 2;
}
for (l = 0; l < count; l++) {
if (br[l] < 2)
break;
}
if (l < count) {
for (int j = 0; j < count; j++) {
lt_add_piece(tbl_temp, part[j]) ;
}
lt_newline(tbl_temp) ;
}
else {
for (int j = 0; j < count; j++) {
lt_add_piece(tbl_slist, part[j]) ;
}
lt_newline(tbl_slist) ;
}
}
lt_delete(tbl1) ;
lt_rename(tbl_temp, tbl1) ;
lt_delete(tbl_slist) ;
end = clock();
if(msg_out){
printf("exec time %f ", (end - start) / 1000.0);
printf("end : %d lines\n", count); fflush(stdout);
}
free(br);
}
// 結果出力
int logic_function(int field, int mask, int bits)
{
int flag = 0;
int i, n, j ;
LogicTable* tbl_in=lt_search(LT_INDEX_TEMP_BASE+field) ;
if(tbl_in==NULL || tbl_in->lines==0){
return 0 ;
}
int line_count=tbl_in->lines ;
int tbl_bitlen=tbl_in->bits ;
uint32_t **line=tbl_in->logic ;
// mask前のビット位置
int conv[12] ;
int pmask=1UL << (bits-1) ;
int pos=0 ;
for(i=0 ; i<bits ; i++){
if(mask & pmask){
conv[pos] = i ;
pos++ ;
}
pmask >>= 1 ;
}
for(i=0 ; i<line_count ; i++){
int sum=0 ;
if (flag == 0)
flag = 1;
else
printf (" + ");
for (n = 0; n < tbl_bitlen; n++) {
sum = 0;
for (j = 0; j < field; j++) {
sum+= (line[i][j] >>(tbl_bitlen-n-1)) & 1 ; // bit[n] ;
}
if (sum == 0) {
if(org_format)
printf ("[`%d]", conv[n]);
else
printf ("%c", 'a'+conv[n]);
}
else if (sum == field) {
if(org_format)
printf ("[%d]", conv[n]);
else
printf ("%c", 'A'+conv[n]);
}
}
}
printf ("\n");
return 0;
}
// maskした時削除できる行か？
int compare_table(uint32_t *table, char *out, int len, uint32_t mask){
if(len<=1) return 0 ;
for(int i=0 ; i<len-1 ; i++){
for(int m=i+1 ; m<len ; m++){
if((table[i] & mask) == (table[m] & mask)){
if(out[i]!=out[m]) return 0 ;
}
}
}
return 1 ;
}
// 不要なビットを削除するマスク
int table_remake(InTable* in_table)
{
int i ;
for(i=0 ; i<MASK_TABLE_SIZE ; i++){ // 2017/09/02 バッファオーバーランの修正
if(compare_table(in_table->logic_arg, in_table->out_arg, in_table->nline, mask_table[i])){
return mask_table[i] ;
}
}
return -1 ; // 矛盾がある
}
// 一回分のデータを作る
int compress(InTable* in_table, int clmn){
int l=0 ;
int i, m ;
printf("\n# Clumn %d ", clmn+1) ;
int mask=table_remake(in_table) ;
if(mask<0){ // 入力に矛盾がある
printf("error table_remake.\n") ;
return -1 ;
}
if(remake==0)
mask=LOGIC_MASK ;
else
printf(" mask[%03x]", mask) ;
in_table->rebuild_mask=mask ;
l=in_table->nline ;
// 出力をパック
for(i=0 ; i<l ; i++){
in_table->logic[i]=in_table->logic_arg[i] & mask ;
in_table->logic[i] |= (in_table->out_arg[i]-'0')<<OUT_MASK_SHIFT ;
in_table->out[i]=in_table->out_arg[i] ;
}
// 未使用のビットを削除して詰める
in_table->nline_rebuild=l ;
in_table->bits=0 ;
mask=in_table->rebuild_mask ;
for(i=0 ; i<l ; i++){
int logic=in_table->logic[i] ;
in_table->logic[i]=0 ;
in_table->out[i]=(logic>>OUT_MASK_SHIFT) + '0' ;
int bit=0 ;
for(m=0 ; m<in_table->logic_bits ; m++){
if(mask & (1UL<<m)){ // 立ってる位置は保存する
in_table->logic[i] |= (logic & (1UL<<m))>>(m-bit) ;
bit++ ;
}
}
// 上位の0のビットを除いた長さ
if(in_table->bits < msb16(in_table->logic[i])+1){
in_table->bits = msb16(in_table->logic[i])+1 ;
}
in_table->logic[i] |= (in_table->out[i]-'0')<<OUT_MASK_SHIFT ;
}
// 上位の0は省略するので、maskの上位はクリアしておく。こうしないと出力時にbit位置がずれるから。
if(remake==0)
mask &= (LOGIC_MASK >> (LOGIC_MAX_BITS - in_table->bits)) ;
// 重複行削除
if(sort_table){
l=sort_and_uniq(in_table->logic, l) ;
in_table->nline_rebuild=l ;
for(i=0 ; i<l ; i++){
in_table->out[i] = (in_table->logic[i]>>OUT_MASK_SHIFT)+'0' ;
}
}
// LogicTable（入力データ）を作成
lt_make(LT_INDEX_IN) ;
lt_setbits(LT_INDEX_IN, in_table->bits) ;
for(i=0 ; i<in_table->nline_rebuild ; i++){
lt_add_piece(LT_INDEX_IN, in_table->logic[i] & LOGIC_MASK) ; // 1行目は出力ビットを削除
}
lt_newline(LT_INDEX_IN) ;
for(i=0 ; i<in_table->nline_rebuild ; i++){
lt_add_piece(LT_INDEX_IN, in_table->logic[i]) ; // 2行目は出力ビット込み
}
printf("\n") ;
// 圧縮
int field = 2;
int res=logic_compress_2(LT_INDEX_IN) ;
while (res == 2) {
res = logic_compress_n(field);
if (res > 0) {
if(resize(field) > 0){
remove_dup(field);
}
}
else{ // 2017/09/01 ここから３行追加
remove_dup(field);
} // ここまで
field <<= 1;
}
// 結果表示
if(msg_out){printf("Result(%d)\n", field);}
while (field) {
logic_function(field, mask, in_table->logic_bits);
field >>= 1;
}
// 後始末
lt_freeall() ;
free_in_table(in_table) ;
return 0 ;
}
InFile in_file[1] ;
InTable in_table[1] ;
int main(int argc, char *argv[])
{
int file=read_opt(argc, argv) ;
if (argc < 2 || file<0) {
printf("Usage : qmc FILE [-r -m -f -s]\n");
printf("\t-r no remake.\n") ;
printf("\t-m message out.\n") ;
printf("\t-f original out format.\n") ;
printf("\t-s sort in table.\n") ;
return 1 ;
}
if (access(argv[file], R_OK) != 0) {
printf("file [%s] not exists.\n", argv[file]);
return 2 ;
}
lt_setup() ;
read_in_file(in_file, argv[file]);
for(int clmn=0 ; clmn < in_file->out_bits ; clmn++){
setup_in_table(in_file, in_table, clmn) ;
compress(in_table, clmn) ;
}
return 0;
}
qmc_misc.c
/*
ロジックテーブル
*/
#include <assert.h>
// #define NODEBUG
// #define DEBUG
#include <unistd.h>
#include <stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <malloc.h>
#include "qmc.h"
#include "qmc_misc.h"
int nlogic_table = 8;
LogicTable *logic_table = NULL;
// バッファが一杯ならlogic、logic_buffをreallocする
static int lt_grow_buff(LogicTable * ptr)
{
int i;
if ((ptr->t_line+1) >= ptr->buff_lines) {
ptr->buff_lines *= 2;
assert((ptr->t_line+1) < ptr->buff_lines) ;
ptr->logic = realloc(ptr->logic, ptr->buff_lines * sizeof(uint32_t *));
}
int buff_size = (ptr->t_line+2) * ptr->pieces * sizeof(uint32_t) ;
if (buff_size > ptr->buff_len) {
while(buff_size >= ptr->buff_len){
ptr->buff_len *= 2 ;
}
ptr->logic_buff = realloc(ptr->logic_buff, ptr->buff_len);
assert(ptr->logic_buff != NULL) ;
// ポインタ付け替え
for (i = 0; i < ptr->t_line; i++) {
ptr->logic[i] = ptr->logic_buff + i * ptr->pieces;
}
}
// linesが増えただけで呼ばれて、確保しているバッファが十分な場合各行のポインタを初期化する
ptr->logic[ptr->t_line] = ptr->logic_buff + ptr->t_line * ptr->pieces;
ptr->logic[ptr->t_line+1] = NULL ;
return ptr->buff_len;
}
static LogicTable *cache_ptr = NULL; // キャッシュ
// indexで探す
// これが返すポインタは、テーブルが増えて再配置された時に未定義になるので注意
LogicTable *lt_search(int index)
{
assert(logic_table != NULL);
LogicTable *ptr;
if (cache_ptr != NULL && cache_ptr->index == index) {
return cache_ptr;
}
int i;
ptr = logic_table;
if (ptr == NULL)
return NULL;
for (i = 0; i < nlogic_table; i++) {
if (ptr->index == index) {
cache_ptr = ptr;
return ptr;
}
ptr++ ;
}
return NULL;
}
// 初期化
int lt_setup(void)
{
assert(logic_table == NULL);
logic_table = malloc(sizeof(LogicTable) * nlogic_table);
int i;
for (i = 0; i < nlogic_table; i++) {
logic_table[i].index = LT_INDEX_NOT_USE;
logic_table[i].logic_buff = NULL;
logic_table[i].logic = NULL;
}
return nlogic_table;
}
LogicTable* lt_make(int index)
{
int i;
assert(logic_table != NULL);
assert(index > 0);
for (i = 0; i < nlogic_table; i++) {
if (logic_table[i].index == index) {
lt_delete(index) ;
}
}
for (i = 0; i < nlogic_table; i++) {
if (logic_table[i].index == LT_INDEX_NOT_USE) {
break;
}
}
if (i == nlogic_table) { // 満員
int old_size = nlogic_table;
nlogic_table *= 2;
cache_ptr=NULL ; // テーブルを移動するので、ポインタキャッシュをクリア
logic_table = realloc(logic_table, sizeof(LogicTable) * nlogic_table);
for (i = old_size + 1; i < nlogic_table; i++) {
logic_table[i].index = LT_INDEX_NOT_USE;
logic_table[i].logic_buff = NULL;
logic_table[i].logic = NULL;
}
i = old_size;
}
LogicTable *ptr = logic_table + i;
ptr->index = index;
ptr->bits = 0;
ptr->pieces = 0;
ptr->lines = 0;
ptr->t_line = 0;
ptr->t_pos = 0;
ptr->buff_lines = 4 ;
ptr->buff_len = 8 ;
ptr->logic_buff = malloc(sizeof(uint32_t) * ptr->buff_len);
ptr->logic = malloc(sizeof(uint32_t **) * ptr->buff_lines);
ptr->logic[0] = ptr->logic_buff ;
ptr->logic[1] = NULL ;
return ptr ;
}
int lt_delete(int index)
{
LogicTable *ptr = lt_search(index);
if (ptr == NULL)
return -1;
if (ptr->buff_len != 0 && ptr->logic != NULL) {
free(ptr->logic);
}
if (ptr->buff_lines != 0 && ptr->logic_buff != NULL) {
free(ptr->logic_buff);
}
ptr->index = LT_INDEX_NOT_USE;
ptr->logic = NULL;
ptr->logic_buff = NULL;
ptr->buff_len = 0;
ptr->buff_lines = 0;
return 1;
}
int lt_newline(int index)
{
LogicTable *ptr = lt_search(index);
if (ptr == NULL)
return -1;
ptr->t_line++;
ptr->t_pos = 0;
lt_grow_buff(ptr);
return -1;
}
void lt_setbits(int index, int bits)
{
LogicTable *ptr = lt_search(index);
if (ptr == NULL)
return;
ptr->bits = bits;
}
int lt_rename(int old_index, int new_index){
LogicTable *ptr = lt_search(old_index);
if (ptr == NULL)
return -1;
ptr->index=new_index ;
return old_index ;
}
// 追加 行があふれたらエラー
int lt_add_piece(int index, uint32_t piece)
{
LogicTable *ptr = lt_search(index);
if (ptr == NULL)
return -1;
if (ptr->t_line == 0) { // １行目なら際限なく追加
if(ptr->lines==0) ptr->lines=1 ;
ptr->pieces++;
lt_grow_buff(ptr);
ptr->logic[ptr->t_line][ptr->t_pos] = piece;
ptr->t_pos++;
}
else { // ２行目以降は１ラインのデータ数に制限がある
if (ptr->t_pos == ptr->pieces) {
return -2;
}
else {
ptr->lines=ptr->t_line+1 ; // linesは要素追加時に更新
ptr->logic[ptr->t_line][ptr->t_pos] = piece;
ptr->t_pos++;
}
}
return ptr->t_pos;
}
void lt_freeall(void){
int i ;
for (i = 0; i < nlogic_table; i++) {
if (logic_table[i].index != 0) {
lt_delete(logic_table[i].index) ;
}
}
}
static const uint32_t popc_table[16] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
// 16bits
int huming_weight16(uint32_t a)
{
a &= 0xffff ;
return
popc_table[a & 0x0f] +
popc_table[(a >> 4) & 0x0f] +
popc_table[(a >> 8) & 0x0f] +
popc_table[(a >> 12) & 0x0f];
}
int msb16(uint32_t v) {
v &= 0xffff ;
if (v == 0) return 0;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
return huming_weight16(v) - 1 ;
}
// 文字列末の改行を削除する
int trim_CRLF(char *str)
{
int l = strlen(str)-1;
if(l>=0){
if (str[l] == '\x0d' || str[l] == '\x0a') {
str[l] = 0;
}
}
l-- ;
if(l>=0){
if (str[l] == '\x0d' || str[l] == '\x0a') {
str[l] = 0;
}
}
return 0;
}
void setup_in_table(InFile* in_file, InTable* in_table, int clmn){
int i, l=0 ;
in_table->logic_bits=in_file->logic_bits ;
in_table->nline=in_file->nline ;
in_table->logic_arg=malloc(sizeof (uint32_t) * (in_file->nline)) ;
in_table->out_arg=malloc(in_file->nline+1) ;
in_table->out_arg[0]=0 ;
in_table->nline_rebuild=0 ;
in_table->rebuild_mask=LOGIC_MASK ;
in_table->logic=malloc(sizeof (uint32_t) * (in_file->nline)) ;
in_table->out=malloc(in_file->nline+1) ;
in_table->out[0]=0 ;
for(i=0 ; i<in_file->nline ; i++){
if(in_file->out[i][clmn]!='x'){ // Don't careの行は除く
in_table->logic_arg[l]=in_file->logic[i] ;
in_table->out_arg[l]=in_file->out[i][clmn] ;
l++ ;
}
}
in_table->nline= l ;
}
void free_in_table(InTable* in_table){
assert(in_table->logic_arg!=NULL) ;
free(in_table->logic_arg) ;
assert(in_table->logic!=NULL) ;
free(in_table->logic) ;
assert(in_table->out_arg!=NULL) ;
free(in_table->out_arg) ;
assert(in_table->out!=NULL) ;
free(in_table->out) ;
}
readfile.c
/*
入力ファイルのパース
*/
#include <assert.h>
// #define NODEBUG
#include <unistd.h>
#include <stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "qmc.h"
#include "qmc_misc.h"
#include "readfile.h"
static signed int parse_line(InFile* in_file, char *line, int pos);
static int count_textsize(char *filename, int *in_file_numline, int *in_file_maxlen);
// in_fileへ行を追加
static signed int parse_line(InFile* in_file, char *line, int pos)
{
int state = 0;
uint32_t logic = 0;
char *out ;
int logic_len=0 ;
int out_buff_len=32 ;
int out_len=0 ;
out=malloc(out_buff_len) ;
while (*line) {
switch (state) {
case 0:
if (*line == ' ' || *line == '\t') {
break;
}
else if (*line == '0' || *line == '1') {
state = 1;
continue;
}
else {
return -2;
}
break;
case 1:
if (*line == '0' || *line == '1') {
logic <<= 1;
logic += *line - '0';
logic_len++ ;
}
else {
state = 2;
continue;
}
break;
case 2: // skip white spaces.
if (*line == ' ' || *line == '\t') {
break ;
}
else{
state=3 ;
continue ;
}
break ;
case 3:
if (*line == '0' || *line == '1' || *line == 'x') {
// out についか、長さがたりなければrealloc @@@
out[out_len]=*line ;
out_len++ ;
}
break;
}
if(out_len>=out_buff_len){
out_buff_len*=2 ;
out=realloc(out, out_buff_len) ;
}
line++;
}
if(state==3){ // 最後まで読んだ
if(out_len==0) return -3 ; // 出力が未定義
out[out_len]=0 ;
if(in_file->logic_bits<logic_len){
in_file->logic_bits=logic_len;
}
in_file->logic[pos]=logic ;
in_file->out[pos]=out ;
return logic ;
}
return -1;
}
int read_in_file(InFile* in_file, char* filename)
{
FILE *fp;
int i ;
char* linebuff ;
int linebuff_len ;
int buffsize = 32;
int nline = 0;
int out_len=0 ;
count_textsize(filename, &buffsize, &linebuff_len) ;
if(buffsize==0 || linebuff_len==0) return 0 ;
in_file->logic_bits=0 ;
in_file->nline=0 ;
in_file->out_bits=0 ;
in_file->logic = malloc((sizeof (uint32_t *)) * buffsize);
in_file->out= malloc((sizeof (char **)) * buffsize);
linebuff_len+=2 ;
linebuff=malloc(linebuff_len) ;
fp = fopen(filename, "r");
for(i=0 ; i<buffsize ; i++){
if(fgets(linebuff, linebuff_len, fp)==NULL){
break ;
}
trim_CRLF(linebuff) ;
int ret = parse_line(in_file, linebuff, nline);
if(ret<0) continue ;
if(out_len<strlen(in_file->out[nline])){
out_len=strlen(in_file->out[nline]) ;
}
nline++;
if (nline > buffsize) {
buffsize *= 2;
in_file->logic = realloc(in_file->logic, (sizeof (uint32_t *)) * buffsize);
in_file->out = (char **)realloc(in_file->out, (sizeof (char **)) * buffsize);
}
}
fclose(fp) ;
in_file->out_bits=out_len ;
for(i=0 ; i<nline ; i++){
if(strlen(in_file->out[i])!=out_len){
int n ;
in_file->out[i]=realloc(in_file->out[i], out_len+1) ;
for(n=strlen(in_file->out[i]) ; n<out_len ; n++){
in_file->out[i][n]='x' ;
}
in_file->out[i][n]=0 ;
}
}
in_file->nline=nline ;
free(linebuff) ;
return nline ;
}
// ファイルの最大行の文字数と行数をカウントする。
#define GET_MAX_CHUNK_SIZE 32
static int count_textsize(char *filename, int *in_file_numline, int *in_file_maxlen)
{
int len = 0;
FILE *fp;
char buff[GET_MAX_CHUNK_SIZE + 1];
in_file_numline[0] = 0 ;
in_file_maxlen[0] = 0;
fp = fopen(filename, "r");
if (fp == NULL) {
return 0;
}
int r_len = 0;
while (1) {
buff[0] = 0;
char *r = fgets(buff, GET_MAX_CHUNK_SIZE + 1, fp);
if (r == NULL)
break;
r_len = strlen(buff);
if (r_len == 0) {
break;
}
else if (buff[r_len - 1] == '\x0d' || buff[r_len - 1] == '\x0a') {
in_file_numline[0]++;
len += r_len - 1;
if (len > in_file_maxlen[0]) in_file_maxlen[0] = len;
len = 0;
}
else {
len += r_len;
}
if (feof(fp)) {
if (len > 0) { // 最後の行が改行無しだった
in_file_numline[0]++;
if (len > *in_file_maxlen)
in_file_maxlen[0] = len;
}
break;
}
}
fclose(fp) ;
return in_file_maxlen[0] ;
}
mask12.c
#include <stdio.h>
static const int popc_table[16] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
// 16bits
int huming_weight16(int a)
{
a &= 0xffff ;
return
popc_table[a & 0x0f] +
popc_table[(a >> 4) & 0x0f] +
popc_table[(a >> 8) & 0x0f] +
popc_table[(a >> 12) & 0x0f];
}
int mask_table[4096+13*2] ;
int main(void){
int i ;
int pos=0 ;
int bit ;
while(bit<=0xfff){
for(i=0 ; i<=0xfff ; i++){
if(huming_weight16(i)==bit){
mask_table[pos]=i ;
pos++ ;
}
}
bit++ ;
}
printf("int mask_table[4096]={\n");
for(i=0 ; i<=0xfff ; i++){
printf("0x%03x, ", mask_table[i]) ;
if((i % 16)==15) printf("\n") ;
}
printf("};\n");
return 0 ;
}
サンプル
# num ABCDEFG
0000 1111110
0001 0110000
0010 1101101
0011 1111001
0100 0110011
0101 1011011
0110 1011111
0111 1110000
1000 1111111
1001 1111011
1010 1110111
1011 0011111
1100 1001110
1101 0111101
1110 1001111
1111 1000111
ToDo
変数名等の見直し
Windowsコンソール対応
マルチプロセス対応
その他
オリジナルを作成したjun6231jpさん。
そのほかコメント欄に改造案など出してくれた方々に感謝します。