WhyCan Forum(哇酷开发者社区)

static double buffer[N]; // N = 2^(k+1)
void fft(const double* src_x, const double* src_y, double* dst_x, double* dst_y, int k) {
    int i, n;
    double temp, temp_x, temp_y;
    if (0 == k) {
        *dst_x = *src_x;
        *dst_y = *src_y;
        return;
    }
    n = 1 << (k - 1);
    for (i = 0; i < n; i++) {
        buffer[i] = src_x[i * 2];
        buffer[i + n] = src_y[i * 2];
        buffer[i + 2 * n] = src_x[i * 2 + 1];
        buffer[i + 3 * n] = src_y[i * 2 + 1];
    }
    fft((const double*)buffer + 2 * n, (const double*)buffer + 3 * n, dst_x, dst_y, k - 1);
    fft((const double*)buffer, (const double*)buffer + n, (double*)buffer + 2 * n, (double*)buffer + 3 * n, k - 1);
    for (i = 0; i < n; i++) {
        temp = i * M_PI / n;
        temp_x = cos(temp);
        temp_y = sin(temp);
        buffer[i] = dst_y[i] * temp_y + dst_x[i] * temp_x;
        buffer[i + n] = dst_y[i] * temp_x - dst_x[i] * temp_y;
        dst_x[i] = buffer[i + 2 * n] + buffer[i];
        dst_y[i] = buffer[i + 3 * n] + buffer[i + n];
        dst_x[i + n] = buffer[i + 2 * n] - buffer[i];
        dst_y[i + n] = buffer[i + 3 * n] - buffer[i + n];
    }
}

#include <stdio.h>
#include <stdint.h>
#include <math.h>

typedef struct {
    float r;
    float i;
}complex;

static void butter_fly(complex* a, complex* b, const complex* c) {
    complex bc;
    bc.r = b->r * c->r - b->i * c->i;
    bc.i = b->r * c->i + b->i * c->r;
    b->r = a->r - bc.r;
    b->i = a->i - bc.i;
    a->r += bc.r;
    a->i += bc.i;
}

static uint32_t bits_reverse(uint32_t index, uint32_t bits) {
    uint32_t left, right;
    left = index << 16;
    right = index >> 16;
    index = left | right;
    left = (index << 8) & 0xff00ff00;
    right = (index >> 8) & 0x00ff00ff;
    index = left | right;
    left = (index << 4) & 0xf0f0f0f0;
    right = (index >> 4) & 0x0f0f0f0f;
    index = left | right;
    left = (index << 2) & 0xc3c3c3c3;
    right = (index >> 2) & 0x3c3c3c3c;
    index = left | right;
    left = (index << 1) & 0xa5a5a5a5;
    right = (index >> 1) & 0x5a5a5a5a;
    index = left | right;
    return index >> (32 - bits);
}

static void fft_k(complex* dat, const complex* w, uint32_t k, uint32_t k_all) {
    uint32_t i, j;
    complex* dat1;
    k_all = 1 << (k_all - k - 1);
    k = 1 << k;
    dat1 = dat + k;
    for (i = 0; i < k_all; i++) {
        for (j = 0; j < k; j++) {
            butter_fly(dat++, dat1++, w + j * k_all);
        }
        dat += k;
        dat1 += k;
    }
}

void fft_init(complex* w, uint32_t k) {
    float beta = 0.0f, dbeta = 3.1415926535f / k ;
    for ( ; k; k--) {
        w->r = cosf(beta);
        w->i = sinf(beta);
        beta += dbeta;
        w++;
    }
}

void fft(complex* dat, const complex* w, uint32_t k) {
    uint32_t i, j, n;
    complex temp;
    n = 1 << k;
    for (i = 0; i < n; i++) {
        j = bits_reverse(i, k);
        if (i <= j) {
            continue;
        }
        temp = dat[i];
        dat[i] = dat[j];
        dat[j] = temp;
    }
    for (i = 0; i < k; i++) {
        fft_k(dat, w, i, k);
    }
}

#define K 4
#define N (1 << K)
static complex w[N / 2];
static complex dat[N];

int main() {
    uint32_t i;
    for (i = 0; i < N; i++) {
        dat[i].r = 0.0f;
        dat[i].i = 0.0f;
    }
    dat[0].r = 1.0f;
    dat[1].r = 1.0f;
    fft_init((complex*)w, N / 2);
    fft((complex*)dat, (const complex*)w, K);
    for (i = 0; i < N; i++) {
        printf((const char*)"dat[%d] = %f + %f * i\n", i, dat[i].r, dat[i].i);
    }
    return 0;
}

%{
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "simple_compiler.tab.h"
#define YY_SKIP_YYWRAP
extern int yylval;
int yylex(void);

static int var_save(char* v) {
	char* p = (char*)malloc(32);
	sprintf(p, "%s", v);
	return (int)p;
}

static int new_var(void) {
	static int index = 0;
	char* p = (char*)malloc(16);
	sprintf(p, "r_%d", index++);
	return (int)p;
}

static int function_paras(int para0, int para1) {
	char* p = (char*)malloc(128);
	sprintf(p, "%s, %s",  (const char*)para0, (const char*)para1);
	free((char*)para0);
	free((char*)para1);
	return (int)p;
}

static int function_call(int func) {
	char* p = (char*)malloc(256);
	sprintf(p, "%s()",  (const char*)func);
	free((char*)func);
	return (int)p;
}

static int function_callp(int func, int paras) {
	char* p = (char*)malloc(256);
	sprintf(p, "%s(%s)",  (const char*)func, (const char*)paras);
	free((char*)func);
	free((char*)paras);
	return (int)p;
}

%}

num [0-9]+
hex "0x"[0-9a-fA-F]+
bin "0b"[01]+
_var [_a-zA-z]+[_a-zA-z0-9]*

_equal "="
_lp_s "("
_rp_s ")"
_split1 ","
_split2 ";"

_plus "+"
_minus "-"
_mul "*"
_divide "/"
_mod "%%"
_shift_r ">>"
_shift_l "<<"
_not "~"
_more ">"
_less "<"
_more_equal ">="
_less_equal "<="
_equal_equal "=="
_not_equal "!="

_next_line [\n]+
space [ \t]+

%%
{num} {
	yylval = var_save(yytext);
	return var;
}
{hex} {
	yylval = var_save(yytext);
	return var;
}
{bin} {
	yylval = var_save(yytext);
	return var;
}
{_var} {
	yylval = var_save(yytext);
	return var;
}

{_lp_s} {
	return lp_s;
}
{_rp_s} {
	return rp_s;
}

{_split1} {
	return split1;
}
{_split2} {
	return split2;
}

{_plus} {
	return plus;
}
{_minus} {
	return minus;
}
{_mul} {
	return mul;
}
{_divide} {
	return divide;
}
{_mod} {
	return mod;
}
{_shift_r} {
	return shift_r;
}
{_shift_l} {
	return shift_l;
}
{_not} {
	return not;
}
{_more} {
	return more;
}
{_less} {
	return less;
}
{_more_equal} {
	return more_equal;
}
{_less_equal} {
	return less_equal;
}
{_equal_equal} {
	return equal_equal;
}
{_not_equal} {
	return not_equal;
}

{_equal} {
	return equal;
}

{_next_line} {
	return next_line;
}
{space} {
}
. {
}

%%

%{
#include <stdio.h>
#define YYSTYPE int
#include "lex.yy.c"
int yyparse(void);
void yyerror(char* s);
%}

%token dig var lp_s rp_s plus minus mul divide mod shift_r shift_l not more less more_equal less_equal equal_equal not_equal equal split1 split2 next_line

%%

code_lines: code_lines code_line next_line {}
	| code_line next_line {}
	;
code_line: code split2 {}
	;
code: var_set {}
	| var_level5 {}
	;
var_set: var equal var_level5 {printf("%s = %s;\n", (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	;
var_level5: var_level5 more var_level4 {$$ = new_var(); printf("%s = %s > %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level5 less var_level4 {$$ = new_var(); printf("%s = %s < %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level5 more_equal var_level4 {$$ = new_var(); printf("%s = %s >= %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level5 less_equal var_level4 {$$ = new_var(); printf("%s = %s <= %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level5 equal_equal var_level4 {$$ = new_var(); printf("%s = %s == %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level5 not_equal var_level4 {$$ = new_var(); printf("%s = %s != %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level4 {$$ = $1;}
	;
var_level4: var_level4 shift_r var_level3 {$$ = new_var(); printf("%s = %s >> %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level4 shift_l var_level3 {$$ = new_var(); printf("%s = %s << %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level3 {$$ = $1;}
	;
var_level3: var_level3 plus var_level2 {$$ = new_var(); printf("%s = %s + %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level3 minus var_level2 {$$ = new_var(); printf("%s = %s - %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level2 {$$ = $1;}
	;
var_level2: var_level2 mul var_level1 {$$ = new_var(); printf("%s = %s * %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
    | var_level2 divide var_level1 {$$ = new_var(); printf("%s = %s / %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
	| var_level2 mod var_level1 {$$ = new_var(); printf("%s = %s %% %s;\n", (char*)$$, (char*)$1, (char*)$3); free((char*)$1); free((char*)$3);}
    | var_level1 {$$ = $1;}
	;
var_level1: var {$$ = $1;}
	| not var {$$ = new_var(); printf("%s = ~%s;\n", (char*)$$, (char*)$1); free((char*)$1);}
	| func_call {$$ = $1;}
	| not func_call {$$ = new_var(); printf("%s = ~%s;\n", (char*)$$, (char*)$1); free((char*)$1);}
	| lp_s var_level5 rp_s {$$ = $2;}
	;
func_call: var lp_s rp_s {$$ = new_var(); printf("%s = %s;\n", (char*)$$, (char*)function_call($1));}
	| var lp_s func_para rp_s {$$ = new_var(); printf("%s = %s;\n", (char*)$$, (char*)function_callp($1, $3));}
	;
func_para: var_level5 {$$ = $1;}
	| func_para split1 var_level5 {$$ = function_paras($1, $3);}
	;
%%
int main(int argc, char *argv[]) {
	return yyparse();
}

int yywrap(void) {
	return 1;
}

void yyerror(char* s) {
	printf("error: %s\n", s);
}

%{
#include <stdio.h>
#include <string.h>
#include "pre_compiler.tab.h"
#define YY_SKIP_YYWRAP
extern int yylval;

int yylex(void);

typedef struct {
	char name[128];
	int init;
	int value;
}var_store;
static var_store var_store_buf[8192];
static int var_store_cnt = 0;

static void exp_store_print(FILE* file, int index) {
	fprintf(file, (const char*)"%s\n", (const char*)var_store_buf[index].name);
}

static int exp_store0(int num) {
	sprintf((char*)var_store_buf[var_store_cnt].name, (const char*)"%d", num);
	var_store_buf[var_store_cnt].init = 0;
	var_store_buf[var_store_cnt++].value = 0;
	return var_store_cnt - 1;
}

static int exp_store1(const char* str, int a) {
	char* p_a;
	if ((a < 0) || (a >= var_store_cnt)) {
		return -1;
	}
	p_a = (char*)var_store_buf[a].name;
	sprintf((char*)var_store_buf[var_store_cnt].name, str, p_a);
	var_store_buf[var_store_cnt].init = 0;
	var_store_buf[var_store_cnt++].value = 0;
	return var_store_cnt - 1;
}

static int exp_store2(const char* str, int a, int b) {
	char* p_a;
	char* p_b;
	if ((a < 0) || (a >= var_store_cnt) || (b < 0) || (b >= var_store_cnt)) {
		return -1;
	}
	p_a = (char*)var_store_buf[a].name;
	p_b = (char*)var_store_buf[b].name;
	sprintf((char*)var_store_buf[var_store_cnt].name, str, p_a, p_b);
	var_store_buf[var_store_cnt].init = 0;
	var_store_buf[var_store_cnt++].value = 0;
	return var_store_cnt - 1;
}

static int exp_store3(const char* str, int a, int b, int c) {
	char* p_a;
	char* p_b;
	char* p_c;
	if ((a < 0) || (a >= var_store_cnt) || (b < 0) || (b >= var_store_cnt) || (c < 0) || (c >= var_store_cnt)) {
		return -1;
	}
	p_a = (char*)var_store_buf[a].name;
	p_b = (char*)var_store_buf[b].name;
	p_c = (char*)var_store_buf[c].name;
	sprintf((char*)var_store_buf[var_store_cnt].name, str, p_a, p_b, p_c);
	var_store_buf[var_store_cnt].init = 0;
	var_store_buf[var_store_cnt++].value = 0;
	return var_store_cnt - 1;
}

static void var_store_init(void) {
	for (var_store_cnt = 4095; ; var_store_cnt--) {
		strcpy((char*)var_store_buf[var_store_cnt].name, (const char*)"");
		var_store_buf[var_store_cnt].value = 0;
		var_store_buf[var_store_cnt].init = 0;
		if (0 == var_store_cnt) {
			break;
		}
	}
}

static int var_store_read(int index) {
	if ((index >= 0) && (index < var_store_cnt) && var_store_buf[index].init) {
		return var_store_buf[index].value;
	}
	return 0;
}

static void var_store_write(int index, int value) {
	if ((index >= 0) && (index < var_store_cnt)) {
		var_store_buf[index].value = value;
		var_store_buf[index].init = -1;
	}
}

static int var_store_find(const char* name) {
	int i;
	for (i = 0; i < var_store_cnt; i++) {
		if (0 == strcmp((const char*)var_store_buf[i].name, name)) {
			return i;
		}
	}
	strcpy((char*)var_store_buf[var_store_cnt].name, name);
	var_store_buf[var_store_cnt].init = 0;
	var_store_buf[var_store_cnt++].value = 0;
	return var_store_cnt - 1;
}

static int is_var_inited(int index) {
	return var_store_buf[index].init;
}

static int bin2num(const char* bin) {
	int num;
	if ('0' != *bin++) {
		return 0;
	}
	if ('b' != *bin++) {
		return 0;
	}
	for (num = 0; *bin; bin++) {
		num <<= 1;
		if ('1' == *bin) {
			num |= 1;
		}
	}
	return num;
}

%}

subwf "subwf"
decf "decf"
addwf "addwf"
comf "comf"
incf "incf"
sublw "sublw"
addlw "addlw"
adcwf "adcwf"
sbcwf "sbcwf"
daa "daa"
das "das"
clrf "clrf"
clrw "clrw"
iorwf "iorwf"
andwf "andwf"
xorwf "xorwf"
rrf "rrf"
rlf "rlf"
swapf "swapf"
bcf "bcf"
bsf "bsf"
andlw "andlw"
xorlw "xorlw"
iorlw "iorlw"
decfsz "decfsz"
incfsz "incfsz"
btfsc "btfsc"
btfss "btfss"
goto "goto"
call "call"
return "return"
retfie "retfie"
retlw "retlw"
movwf "movwf"
movf "movf"
movlw "movlw"
nop "nop"
option "option"
tris "tris"
sleep "sleep"
clrwdt "clrwdt"
int "int"

equ "equ"
org "org"
end "end"
label ":"
split ","
note ";"[^\n]*
next_line [\n]
space [ \t]+

plus "+"
minus "-"
times "*"
divide "/"
lp "("
rp ")"

num [0-9]+
hex1 "0x"[0-9a-fA-F]+
hex2 [0-9]+[0-9a-fA-F]*[hH]
bin "0b"[01]+
var [_a-zA-z]+[_a-zA-z0-9]*

%%
{subwf} {
	yylval = var_store_find(yytext);
	return SUBWF;
}
{decf} {
	yylval = var_store_find(yytext);
	return DECF;
}
{addwf} {
	yylval = var_store_find(yytext);
	return ADDWF;
}
{comf} {
	yylval = var_store_find(yytext);
	return COMF;
}
{incf} {
	yylval = var_store_find(yytext);
	return INCF;
}
{sublw} {
	yylval = var_store_find(yytext);
	return SUBLW;
}
{addlw} {
	yylval = var_store_find(yytext);
	return ADDLW;
}
{adcwf} {
	yylval = var_store_find(yytext);
	return ADCWF;
}
{sbcwf} {
	yylval = var_store_find(yytext);
	return SBCWF;
}
{daa} {
	yylval = var_store_find(yytext);
	return DAA;
}
{das} {
	yylval = var_store_find(yytext);
	return DAS;
}
{clrf} {
	yylval = var_store_find(yytext);
	return CLRF;
}
{clrw} {
	yylval = var_store_find(yytext);
	return CLRW;
}
{iorwf} {
	yylval = var_store_find(yytext);
	return IORWF;
}
{andwf} {
	yylval = var_store_find(yytext);
	return ANDWF;
}
{xorwf} {
	yylval = var_store_find(yytext);
	return XORWF;
}
{rrf} {
	yylval = var_store_find(yytext);
	return RRF;
}
{rlf} {
	yylval = var_store_find(yytext);
	return RLF;
}
{swapf} {
	yylval = var_store_find(yytext);
	return SWAPF;
}
{bcf} {
	yylval = var_store_find(yytext);
	return BCF;
}
{bsf} {
	yylval = var_store_find(yytext);
	return BSF;
}
{andlw} {
	yylval = var_store_find(yytext);
	return ANDLW;
}
{xorlw} {
	yylval = var_store_find(yytext);
	return XORLW;
}
{iorlw} {
	yylval = var_store_find(yytext);
	return IORLW;
}
{decfsz} {
	yylval = var_store_find(yytext);
	return DECFSZ;
}
{incfsz} {
	yylval = var_store_find(yytext);
	return INCFSZ;
}
{btfsc} {
	yylval = var_store_find(yytext);
	return BTFSC;
}
{btfss} {
	yylval = var_store_find(yytext);
	return BTFSS;
}
{goto} {
	yylval = var_store_find(yytext);
	return GOTO;
}
{call} {
	yylval = var_store_find(yytext);
	return CALL;
}
{return} {
	yylval = var_store_find(yytext);
	return RETURN;
}
{retfie} {
	yylval = var_store_find(yytext);
	return RETFIE;
}
{retlw} {
	yylval = var_store_find(yytext);
	return RETLW;
}
{movwf} {
	yylval = var_store_find(yytext);
	return MOVWF;
}
{movf} {
	yylval = var_store_find(yytext);
	return MOVF;
}
{movlw} {
	yylval = var_store_find(yytext);
	return MOVLW;
}
{nop} {
	yylval = var_store_find(yytext);
	return NOP;
}
{option} {
	yylval = var_store_find(yytext);
	return OPTION;
}
{tris} {
	yylval = var_store_find(yytext);
	return TRIS;
}
{sleep} {
	yylval = var_store_find(yytext);
	return SLEEP;
}
{clrwdt} {
	yylval = var_store_find(yytext);
	return CLRWDT;
}
{int} {
	yylval = var_store_find(yytext);
	return INT;
}

{equ} {
	yylval = var_store_find(yytext);
	return EQU;
}
{org} {
	yylval = var_store_find(yytext);
	return ORG;
}
{end} {
	yylval = var_store_find(yytext);
	return END;
}
{label} {
	return LABEL;
}
{split} {
	return SPLIT;
}
{next_line} {
	return NEXT_LINE;
}
{space} {
}
{note} {
}

{num} {
	sscanf(yytext, "%d", &yylval);
	return NUM;
}
{hex1} {
	sscanf(yytext, "0x%x", &yylval);
	return NUM;
}
{hex2} {
	sscanf(yytext, "%x", &yylval);
	return NUM;
}
{bin} {
	yylval = bin2num(yytext);
	return NUM;
}
{plus} {
	return PLUS;
}
{minus} {
	return MINUS;
}
{times} {
	return TIMES;
}
{divide} {
	return DIVIDE;
}
{lp} {
	return LP;
}
{rp} {
	return RP;
}
{var} {
	yylval = var_store_find(yytext);
	if (is_var_inited(yylval)) {
		yylval = var_store_read(yylval);
		return NUM;
	}
	else {
		return VAR;
	}
}

. {
}

%%

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int bool;
#define false (-1)
#define true (0)

static bool char_check(char c) {
    if (c > '9') {
        return false;
    }
    if (c < '0') {
        return false;
    }
    return true;
}

static bool str_check(const char* src) {
    for ( ; *src; src++) {
        if (false == char_check(*src)) {
            return false;
        }
    }
    return true;
}

static void str_reverse(char* s) {
    char temp;
    char* r = s + strlen(s) - 1;
    while (s < r) {
        temp = *s;
        *s++ = *r;
        *r-- = temp;
    }
}

static bool char_add(char a, char b, char* c, char* d) {
    if (false == char_check(a)) {
        return false;
    }
    if (false == char_check(b)) {
        return false;
    }
    a -= '0';
    b -= '0';
    *d = a + b + (*c);
    if (*d > 9) {
        *d -= 10;
        *c = 1;
    }
    else {
        *c = 0;
    }
    *d += '0';
    return true;
}

static bool str_add(const char* a, const char* b, char* d) {
    char aa, bb, c = 0;
    int len_a = strlen(a), len_b = strlen(b);
    char* p_a = a + len_a - 1;
    char* p_b = b + len_b - 1;
    char* p_d = d;
    if (false == str_check(a)) {
        return false;
    }
    if (false == str_check(b)) {
        return false;
    }
    for ( ; (len_a > 0) || (len_b > 0); ) {
        aa = len_a > 0? *p_a-- : '0';
        bb = len_b > 0? *p_b-- : '0';
        char_add(aa, bb, &c, p_d++);
        len_a--;
        len_b--;
    }
    str_reverse(d);
    return true;
}

int main()
{
    char* a = "16664129129421912941294";
    char* b = "34666666666543854397591";
    char c[100] = "";
    str_add(a, b, c);
    printf("%s!\n", c);
    return 0;
}