Twitter Backup Script 2
05/15/2010, 14:45 - Open Source
修改加上日期及在 META 中放上 Twitts 數量,以備後用。

我的 Twitter 備份


#!/bin/sh
#
USER=Tasuka
DATE=`date +%m%d%y`
FILENAME=/tmp/twitter_backup.$DATE.html
#
MAX=`curl "http://api.twitter.com/1/statuses/user_timeline/$USER.xml?page=1&count=20" | \
grep "<statuses_count>" | \
awk -F">" '{print $2}' | \
awk -F"<" '{print $1}' | \
sort | \
awk '{if ($1>NF) NF=$1} END {print NF}'`

if [ $MAX -ge 3200 ];then
MAX=3200
fi

PAGE=$((MAX%200))

if [ $PAGE != 0 ];then
PAGE=$((MAX/200))
PAGE=$((PAGE+1))
else
PAGE=$((MAX/200))
fi

echo "<HTML LANG=UTF8><META NAME=\"TWITTES\" CONTENT=\"$MAX\"> \
<HEAD><TITLE>$USER@Twitter Backup</TITLE></HEAD><BODY><H3>" > \
$FILENAME

i=1
while [ $i -le $PAGE ]; do
curl "http://api.twitter.com/1/statuses/user_timeline/$USER.xml?page=$i&count=200" | \
sed -e "/>/s/>/</g" | \
awk -F"<" 'BEGIN{ flag=0 } \
{ \
if($2=="status" && flag==1){ \
flag=0 \
} \
if($2=="created_at" && flag==0){ \
printf "<BR>%s<BR>",$3 \
} \
if($2=="text"){ \
printf "%s<BR>",$3 \
} \
if($2=="user"){ \
flag=1 \
} \
}' | \
sed -e "/+0000/s/+0000//g" >> $FILENAME
i=$((i+1))
MAX=$((MAX-1))
done

echo "</BODY></HTML>" >> $FILENAME


發表回應 發表回應 ( 566預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 2.8 / 353 )

Twitter Backup Script
05/13/2010, 22:48 - Open Source
上次看了 hao520 在 Twitter 和他的 blog 中談到 Twitter 有可視最後3200推的數量問題,連帶而來的備份的問題。看了還真的有人在作 backup,hao520自已也做了一個 script,不過他是直接從 twitter 的網頁拿資料。一時技癢就也自已作了一個 bash script,是經由 twitter API 而來的。目前顯示出來的資料,沒有編號、也沒有日期,所以還有改善的空間。

以下是備份下來的HTML內容:




再來是程式碼

#!/bin/sh
#
USER=Tasuka
#
MAX=`curl "http://api.twitter.com/1/statuses/user_timeline/$USER.xml?page=1&count=20" \
|grep "<statuses_count>"|awk -F">" '{print $2}' \
|awk -F"<" '{print $1}'|sort| \
awk '{if ($1>NF) NF=$1} END {print NF}'`

if [ $MAX -ge 3200 ];then
MAX=3200
fi

PAGE=$((MAX%200))

if [ $PAGE != 0 ];then
PAGE=$((MAX/200))
PAGE=$((PAGE+1))
else
PAGE=$((MAX/200))
fi

i=1
DATE=`date +%m%d%y-%H%M`

echo "<HTML LANG=UTF8><HEAD><TITLE>$USER Twitter Backup</TITLE> \
</HEAD><BODY><H3>" > /tmp/twitter_backup.$DATE.html
while [ $i -le $PAGE ]; do
curl "http://api.twitter.com/1/statuses/user_timeline/$USER.xml?page=$i&count=200" \
|grep '<text>' | awk -F"<text>" '{print $2}' | \
awk -F"</text>" '{printf "%s<BR>",$1}' >>/tmp/twitter_backup.$DATE.html
i=$((i+1))
MAX=$((MAX-1))
done
echo "</BODY></HTML>" >>/tmp/twitter_backup.$DATE.html

發表回應 發表回應 ( 452預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 242 )

數字會說話,但你懂了數字要告訴你什麼?
05/10/2010, 16:53 - 生活
很多人都經常會說:數字會說話。但是經常流於只看表象,而看不到數字真正代表的意義。數字就是數字,數字本身簡單說來只有數字。要看出不同,至少要有兩個或兩個以上的數字作比較,才看得出不同。比較方法不外乎加、減、乘、除等運算方式。比如說:考試60分,這件事,一般人直覺會認為考得不好,因為他是拿常用的標準100來和60相比,只得到3/5的分數。但若是再說明有100人參加考試,而得最高分的就是60,這時好像60又是非常棒的數字了,因為是最高分數啊。但如果說100人中有99個都是60的話呢?那60馬上又變得沒什麼了不起了,有99/100的人都一樣拿到這個分數。由上例可知,單單一個數字,沒什麼意義,數字的意義需要附屬的數字,放在一起之後,數字才變得有意思。

不過大多數的人看數字,只是很簡單的和自已心中的數字相比,而得到好、或不好的結論。但這個好或不好經常和事實有一定的距離。比如說警方的效率指標中,有一項破案率。數字高代表比較好,一般人就會根據這個數字的高低而自已得到破案率高,代表治安比較好這個印象。但事實上並不盡然喔!假設台北市某區的單月破案率是99%,而蘭嶼島的單月破案率是0%。光從數字看是台北市優於蘭嶼,而得到蘭嶼治安不好,因為破案率是零。不過大家一定忘了,破案率高,代表犯罪件數可能也高,所以破案率高不代表治安好吧。如台北市一天的犯罪件數是1000件,而破案率99%,就是990件,還有10件沒破;而蘭嶼可能100天發生不到一件案件,而且沒有偵破,所以破案率是0%。若是真的要比起來的話,台北市一百天應會有(1000*100)*(100-99)%=1000件沒破案,比上蘭嶼一百天發生一件案件,同樣沒有破案,哪𥚃的治安好呢?當然人口數不同,若台北市某區的人口數是蘭嶼的十倍、每日進出人數是百倍的話,也還是遠遠高過蘭嶼,這樣的數字相比還是失真,只是利用來說明,不可以單只看數字本身,要連同數字背後的意義一起分析才有意思。

現在很流行民調,經常會看到發表民調如何、如何,所以得到的是某一類的答案。單只因數字而簡單得到答案,又是一種失真。因為調查的樣本數遠低於實際的人口數、調查的範圍是否合理、調查的方式是否合理、調查時的問卷題目是否有暗中誤導、調查的時間,調查當時的態度,都會影響結果。經常發生的是有多方,同時對某問題,作出來的民調,兩方得到的結論,根本南轅北轍,而互相質疑。事實上兩方的數字,可能根本因上面的理由,而有非常大的誤差,和事實相比,都是嚴重失真下得到的結論。

同樣的,一家公司中,經常會對員工個人、或是整個單位作效能評比,甚至於對客戶的反應,也是一樣經常流於失真。例如對員工個人的評比,經常簡化到以工作時間長短,作為基準,時間長的就是比較好。但事實上一個一天工作八小時,但可以準時交出需求的工程師,應該要比一天工作十四小時,一樣準時交出所需求的工程師要好太多了。8:14,當然低的好不是嗎?但是因為只工作八小時的工程師,沒有配合加班,所以直接而簡單的印象就是不好。而在作單位評比時也是一樣,一個單位經常可以準時交付客戶需求的東西,而且沒有發生重大問題,硬是比同樣交付客戶需求的東西,但是到處充滿了問題的要不好,理由很簡單,因為作好是正常的,沒有發生問題,所以單位的能見度低,而經常發生問題而且解決的單位,因為經常出現問題、並快速反應,所以直覺的得到“很努力、並且很有效率,但這些人都忽略了"No news is good news"的真正意思。又例如代工單位因為幫客戶解決問題,而使得客戶可以將付出減少支出。但在高層看來,直覺的看到的數字是,客戶的需求變少,而認為該單位不努力,使得客戶減少支付代工費,這也是只看表面而直接得到的結論。事實上以代工業而言,客戶之所以要用代工,就是要減低支出,而幫客戶達到這個要求,應該是高效率才對。而且經常因為簡單的看數字作決策,而作出錯誤而且不利於客戶的決策,接到客戶的抱怨時,直覺認定是該負責單位有問題,事實上客戶在報怨的,可能是因高層的特意忽視客戶需求而作出的決策,而非關實際工作的單位。不過通常這種高層都不會認為是自已不會看數字、不了解客戶反應、以及自已決策時的故意錯判的錯。而在面對客戶時說的都不是人話而是鬼話了。這樣子生意還做得下去,還真的是見鬼了。

現代人是生活在充滿數字的時代,各種數字除了表面的意義,經常還有其背面潛在的意義,要經過嚴格的分析才有可能得到比較接近真象的結論,若只是經由數字的表象,就得到結論,那何必花錢請這些人位居高層、握有決策?要這麼簡單的看數字的高低或打印象分數,請個小學二年級的已經學過四則運算的小學生來,就可以簡單無誤的指出那個數字高、那個數字低了,不然也可以直接用Excel就可以作出決策了不是嗎?所以說:“數字會說話,但說出來的是人話還是鬼話,是和看的人會不會分析,並看到數字背後的意義有關“。不是簡單到用一句鬼話就可以帶過的。
3 回應 3 回應 ( 1416預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 2.9 / 409 )

使用BGP連接兩個不直接相連的網路
04/28/2010, 11:53 - Network
使用BGP連接兩個不直接相連的網路
發表回應 發表回應 ( 2096預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 382 )

換光世代10M/2M
04/23/2010, 22:33 - 今天
今天施工完成,使用的是ZyXel的VDSL2的Modem,有四個Ethernet Port。不過電話線要先經過Modem再至電話機,可以能是為了減少干擾吧。
換了之後由原來的ADSL 2M/256Kbps bridge mode固定一個IP換成PPPoE 8個浮動IP,但這個工作站是在家裡,需再用固定IP,所以再至So-net網頁換成PPPoE 1個固定IP加7個浮動IP。申請都可以在網頁上簡單完成,不過在要作IP反解Domain Name設定時,發現還是被鎖定在原來的ADSL的IP,造成無法自已作IP反解,這時只有求助服務人員了。撥過電話之後,因為是星期五晚上,所以需要到下星期才會解除原先IP的設定。所以現在是DNS正解是由自已的DNS Server和Seednet的Domain Name Server已經設定完成。而反解就只有等到下週一或二了。

設再來就是測速了,若是用So-net提供的測試,就不太準了,而且So-net才用10/20/30/40MB的檔安經由HTTP download,檔案太小了。正好Apple昨天開放了支援iPad的新XCode 3.2.2,所以就由 http://developer.apple.com 拿新的 XCode 3.2.2 for Mac OS with iPad 2.31GB的檔案來試,檔案夠大,應該會準一點吧!

測試如下
開始

中間

看來一直在1.1MB,所以傳輸速度就大約是 1.1MBx8bit=8.8Mbps的下載速度。上傳的話,目前沒有相近速度的Server可以測試,所以不知道,應該也不會太差吧。
每秒8.8Mbps已經和10BaseT的速度一樣了,不過當然和Firewire 400Mbps相比還是差很多啦!
最後將檔案經由Fireware copy至備份硬碟上。

2.31GB的檔案用Firewire傳2分鐘
2.31GBx8x1000)/120=154Mbps
USB2.0的話,我沒有這種設備,反正也不可能快到哪裡去,就算了吧!因為USB的兩個device一定要經由Host才可以交換資料,所以要視Host的處理速度而定。而Firewire Device是可以自已溝通的,不需要Host幫助,速度當然大大的不同了。

PS:在外面,收家中的電子郵件,Server傳輸可達700KB=5.6Mbps,有沒有這麼好啊!
發表回應 發表回應 ( 521預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 444 )

還我複決權
04/22/2010, 22:55 - 想到的
聽說憲法中有規定,人民有選舉、罷免、創制、複決四項權利,但是好像到目前唯一還要經由民意代表行使的只有複決權。這幾天,立法院又開始大打出手,各說各話,難道我們就只能交給那一百多個立法委員決定一切事情?聽憑政黨協商,內線交易?只可以看著政府將手介到大家的口袋、衣袋、外褲、內褲的掏錢,但卻因為是立法院通過的法案,或政府不交給民意機關監督,而完全沒有辦法,只可以在下一次選舉到來之前,懊悔選錯人?

我要說的是請政府“還我複決權“,政府機關及民意機關通過的法案,需經過公民投票複決之後才可以算是正式通過,反正台灣現在每年選舉場子也不少,不差多一點。如此正好可以完全解決假民意、真黨意,假民主、真金主。 參考一下2008加州公投 http://tinyurl.com/2dv8vlm
發表回應 發表回應 ( 480預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 2.9 / 388 )

QR Code 印章
04/22/2010, 22:46 - Misc
最近都在研究 QR Code 的演算法,想想就去刻印行製作了一個小印,當作藏書印。事實上也很簡單,將圖檔傳給刻印行,說明尺寸及材質,一天就可以拿到了,我作的這顆收我40元啦。要產生圖檔網路上找一下就有了,要解碼的話,可以拿到的就更多了,可以裝在手機、電腦、iPhone、Notebook...。印在紙上,可以解碼沒有問題,只要印泥不要太多,不要用力,就可以了。用什麼顏色的印泥都可以,不過對比色高一點比較好辦認。

原始圖檔


印章掃描



2 回應 2 回應 ( 873預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 417 )

BCH(15,5) Error Correction for Objective-C
04/13/2010, 22:02 - Open Source
BCH(15,5) class for Objective-C。參考 http://en.wikipedia.org/wiki/BCH_code
這個 class 說起也不算是我寫的,是修改 Masayuki Miyazaki 寫的 QRCode Java 程式中的 BCH_15_5.java 片斷,只是簡單的改成 Objective-C 而已。


//
// BCH_15_5.h
// BCHTest
//
// Created by Tasuka Hsu on 04/13/2010.
// Copyleft 2010 http://Tasuka.IDV.TW.
//

#import <Foundation/Foundation.h>

@interface BCH_15_5 : NSObject {
}
-(unsigned int)encode:(unsigned int)data;
-(unsigned int)decode:(unsigned int)data;
@end



//
// BCH_15_5.m
// BCHTest
//
// Created by Tasuka Hsu on 04/13/2010.
// Copyleft 2010 http://Tasuka.IDV.TW.
//
// Based on Masayuki Miyazaki
// http://sourceforge.jp/projects/reedsolomon/


#import "BCH_15_5.h"
#define TABLE_SIZE 32

@interface BCH_15_5 (Private)
const unsigned int GX=0x137; /* 0000000100110111 */
unsigned int *trueCodes=NULL;

-(void)makeTrueCodes;
-(unsigned int)slowEncode:(unsigned int)data;
-(int)calcDistance:(unsigned int)c1:(unsigned int)c2;
@end

@implementation BCH_15_5

-(id)init
{
if(![super init]){
return nil;
}

if((trueCodes=(unsigned int *)malloc(TABLE_SIZE*sizeof(unsigned int)))==NULL){
return nil;
}

[self makeTrueCodes];
return self;
}

-(void)dealloc
{
if(trueCodes!=NULL){
free(trueCodes);
}

[super dealloc];
}

-(void)makeTrueCodes
{
for(int i=0;i<TABLE_SIZE;i++){
trueCodes=[self slowEncode:i];
}
}

-(unsigned int)slowEncode:(unsigned int)data
{
unsigned int wk=0;
data<<=5;

for(int i=0;i<5;i++){
wk<<=1;
data<<=1;

if(((wk^data)&0x400)!=0){
wk^=GX;
}
}
return(data&0x7c00)|(wk&0x3ff);
}

-(unsigned int)encode:(unsigned int)data
{
return trueCodes[data&0x1f];
}

-(unsigned int)decode:(unsigned int)data
{
data&=0x7fff;

for(int i=0;i<TABLE_SIZE;i++){
unsigned int code=trueCodes;
if([self calcDistance:data:code]<=3){
return code;
}
}
return -1;
}

-(int)calcDistance:(unsigned int)c1:(unsigned int)c2
{
int n=0;
unsigned int wk=c1^c2;

while(wk!=0) {
if((wk&1)!=0){
n++;
}
wk>>=1;
}
return n;
}

@end



#import <Foundation/Foundation.h>
#import "BCH_15_5.h"

int main (int argc, const char * argv[]) {
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

unsigned int i,j,k,c=19;

BCH_15_5 *bche=[[BCH_15_5 alloc] init];
i=[bche encode:c];
k=i;

printf("BCH_15_5 encode %d",c);

printf(" 0b");
for(int j=0;j<15;j++){
printf("%1d",((i<<=1)&0x8000)?1:0);
}
printf("\n");

[bche release];

// Add random noise
srandom(time(NULL));
unsigned int n=random();

switch(n%3){
case 0:
n&=0x000f;
break;
case 1:
n&=0x00f0;
break;
case 2:
n&=0x0f00;
break;
case 3:
n&=0xf000;
break;
default:
break;
}

printf("add noise=0x%x\n",n);
k^=n;

BCH_15_5 *bchd=[[BCH_15_5 alloc] init];
i=[bchd decode:k];

printf("BCH_15_5 decode 0x%x correct 0x%x\n",k,i);
k=i;

printf("0b");
for(j=0;j<15;j++){
printf("%1d",((i<<=1)&0x8000)?1:0);
}
printf("\n");
k&=0xfd00;

i=k;

printf("Code is 0b");
for(j=0;j<5;j++){
printf("%1d",((i<<=1)&0x8000)?1:0);
}

k>>=10;
printf(" %d\n",k);

[bchd release];

[pool drain];
return 0;
}

發表回應 發表回應 ( 639預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3.1 / 410 )

OS X 10.6.3 update
03/30/2010, 11:02 - Apple
先用 yasu 整理系統,清出了約 3GB 的空間.再作更新!


發表回應 發表回應 ( 678預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 358 )

rscode-objc project in GoogleCode
03/26/2010, 16:51 - Open Source
因為想要做點有趣的實驗,會用到 ReedSolomon FEC 演算法,
網路上有 Java 或 C 版本,但沒找到 Objective-C 可直接用的程式碼.
所以就花了一點時間,參考了 Java 和 C 的版本,做了一個 Objective-C 的版本
給 XCode 在 OS X 下使用,並放到 GoogleCode 上作管理.

原來是想直接用 C 的版本,但在改寫的過程中, 發現原來的程式用了很多的 for loop,
及使用了 array 的資料形態.
後來修改為使用 pointer 和 malloc 動態使用記憶體,並用 memset 和 memcpy 減少了 for loop 的使用.

這個 class 應該可以不用修改就可以經由 GNUStep 搬到各個平台下使用.

想要帶回家玩的可以用 svn checkout http://rscode-objc.googlecode.com/svn/trunk/ rscode-objc-read-only 到 GoogleCode 的 svn 下載

原本 C 語言版本的 rscode 是版權是 GPL, 而商業版要收費的, 而我只是修改, 所以也算是 GPL.
不過我想不收錢, 應該也收不到錢, 因為只是修改,所以也不能收錢.
有注意看的話,在程式開頭權利宣告我是用 Copyleft 而不是 Copyright. XD.


參考資料
http://reedsolomon.sourceforge.jp Java 版 ReedSolomon
http://rscode.sourceforge.net C 語言版本.
http://rscode-objc.googlecode.com GoogleCode Project

程式
RSEncodeDecode.h

//
// RSEncodeDecode.h
// RSCode
//
// Created by Tasuka Hsu on 03/25/2010.
// Copyleft 2010 http://Tasuka.IDV.TW.
// Original C Source code is from http://rscode.sourceforge.net
// and reference to Java Source code from http://reedsolomon.sourceforge.jp

#import <Foundation/Foundation.h>
#import <stdio.h>
#import <stdlib.h>

#define PPOLY 0x1d

/*
Below is NPAR, the only compile-time parameter you should have to
modify.
It is the number of parity bytes which will be appended to
your data to create a codeword.
Note that the maximum codeword size is 255, so the
sum of your message length plus parity should be less than
or equal to this maximum limit.
In practice, you will get slooow error correction and decoding
if you use more than a reasonably small number of parity bytes.
(say, 10 or 20)
*/
#define NPAR 17

/* Maximum degree of various polynomials. */
#define MAXDEG (NPAR*2)

#define TABLESIZE 256

@interface RSEncodeDecode : NSObject {
@public
int npar;
int maxdeg;
int length;

int *gExp;
int *gLog;

// Encoder parity bytes
int *pBytes;
// Decoder syndrome bytes
int *synBytes;
// generator polynomial
int *genPoly;
// The Error Locator Polynomial, also known as Lambda or Sigma. Lambda[0]==1
int *Lambda;
// The Error Evaluator Polynomial
int *Omega;

@private
// error locations found using Chien's search
int *ErrorLocs;
int NErrors;

// erasure flags
int *ErasureLocs;
int NErasures;
}

-(void)setNPAR:(int)n;
-(void)setLength:(int)n;
-(BOOL)initTables;
-(void)freeTables;

// Reed Solomon encode/decode routines
-(void)initializeECC;
-(int)checkSyndrome;
-(void)deCode:(unsigned char *)data:(int)l;
-(void)deCode:(unsigned char *)data;
-(void)deCode:(unsigned char *)data:(int)l:(int)n;

-(void)enCode:(unsigned char *)msg:(int)l:(unsigned char *)dst;
-(void)enCode:(unsigned char *)msg:(unsigned char *)dst;
-(void)enCode:(unsigned char *)msg:(int)l:(unsigned char *)dst:(int)nl;

// CRC-CCITT checksum generator
-(short int)crcCCITT:(unsigned char *)msg:(int)len;
-(short int)crcHWare:(short int)data:(short int)genpoly:(short int)accum;

-(void)initGaloisTables;
-(int)gInv:(int)a;
-(int)gMul:(int)a:(int)b;

/* Error location routines */
-(int)correctErrorsErasures:(unsigned char *)codeword:(int)csize:(int)nerasures:(int *)erasures;

-(void)modifiedBerlekampMassey;
/* polynomial arithmetic */
-(void)addPolys:(int *)dst:(int *)src;
-(void)scalePoly:(int)k:(int *)poly;
-(void)mulPolys:(int *)dst:(int *)p1:(int *)p2;
-(void)copyPoly:(int *)dst:(int *)src;
-(void)zeroPoly:(int *)poly;
-(void)findRoots;

/* local ANSI declarations */
-(int)computeDiscrepancy:(int *)lambda:(int *)S:(int)L:(int)n;
-(void)computeGenPoly:(int)l:(int *)genpoly;
-(void)initGamma:(int *)gamma;
-(void)computeModifiedOmega;
-(void)computeNextOmega:(int)d:(int *)A:(int *)dst:(int *)src;
-(void)mulzPoly:(int *)src;
-(void)zeroFillFrom:(unsigned char *)buf:(int)from:(int)to;

// debugging routines
-(void)printParity;
-(void)printSyndrome;
@end


RSEncodeDecode.m

//
// RSEncodeDecode.m
// RSCode
//
// Created by Tasuka Hsu on 03/25/2010.
// Copyrleft 2010 http://Tasuka.IDV.TW.
// Original C Source code from http://rscode.sourceforge.net
// and reference to Java Source code from http://reedsolomon.sourceforge.jp

#import "RSEncodeDecode.h"

@implementation RSEncodeDecode
/* This is one of 14 irreducible polynomials
* of degree 8 and cycle length 255. (Ch 5, pp. 275, Magnetic Recording)
* The high order 1 bit is implicit */
/* x^8 + x^4 + x^3 + x^2 + 1 */

-(id)init
{
if(![super init]){
return nil;
}
npar=NPAR;
maxdeg=npar*2;
length=0;

if([self initTables]!=TRUE){
NSLog(@"Memory allocated error\n");
return nil;
}

[self initializeECC];

return self;
}

-(void)dealloc
{
[self freeTables];
[super dealloc];
}

-(void)setNPAR:(int)n
{
npar=n;
maxdeg=npar*2;

[self freeTables];

if([self initTables]!=TRUE){
NSLog(@"Memory allocated error\n");
return;
}

[self initializeECC];
}

-(void)setLength:(int)n
{
length=n;
}

-(BOOL)initTables
{
if((gExp=(int *)malloc(sizeof(int)*TABLESIZE*2))==NULL){
return FALSE;
}
if((gLog=(int *)malloc(sizeof(int)*TABLESIZE))==NULL){
free(gExp);
return FALSE;
}
if((pBytes=(int *)malloc(sizeof(int)*maxdeg))==NULL){
free(gExp);
free(gLog);
return FALSE;
}
if((synBytes=(int *)malloc(sizeof(int)*maxdeg))==NULL){
free(gExp);
free(gLog);
free(pBytes);
return FALSE;
}
if((Lambda=(int *)malloc(sizeof(int)*maxdeg))==NULL){
free(gExp);
free(gLog);
free(pBytes);
free(synBytes);
return FALSE;
}
if((Omega=(int *)malloc(sizeof(int)*maxdeg))==NULL){
free(gExp);
free(gLog);
free(pBytes);
free(synBytes);
free(Lambda);
return FALSE;
}
if((genPoly=(int *)malloc(sizeof(int)*maxdeg*2))==NULL){
free(gExp);
free(gLog);
free(pBytes);
free(synBytes);
free(Lambda);
free(Omega);
return FALSE;
}
if((ErrorLocs=(int *)malloc(sizeof(int)*maxdeg*2))==NULL){
free(gExp);
free(gLog);
free(pBytes);
free(synBytes);
free(Lambda);
free(Omega);
free(genPoly);
return FALSE;
}
if((ErasureLocs=(int *)malloc(sizeof(int)*maxdeg*2))==NULL){
free(gExp);
free(gLog);
free(pBytes);
free(synBytes);
free(Lambda);
free(Omega);
free(genPoly);
free(ErrorLocs);
return FALSE;
}
return TRUE;
}

-(void)freeTables
{
if(gExp!=NULL){
free(gExp);
}
if(gLog!=NULL){
free(gLog);
}
if(pBytes!=NULL){
free(pBytes);
}
if(synBytes!=NULL){
free(synBytes);
}
if(Lambda!=NULL){
free(Lambda);
}
if(Omega!=NULL){
free(Omega);
}
if(genPoly!=NULL){
free(genPoly);
}
if(ErrorLocs!=NULL){
free(ErrorLocs);
}
if(ErasureLocs!=NULL){
free(ErasureLocs);
}
}

// Initialize lookup tables, polynomials, etc.
-(void)initializeECC
{
// Initialize the galois field arithmetic tables
[self initGaloisTables];
// Compute the encoder generator polynomial
[self computeGenPoly:npar:genPoly];
}

-(void)initGaloisTables
{
// initialize the table of powers of alpha
register int i,d=1;

for(i=0;i<TABLESIZE-1;i++){
gExp=gExp[TABLESIZE-1+i]=d;
gLog[d]=i;
d<<=1;
if((d&0x100)!=0){
d=(d^PPOLY)&0xff;
}
}
}

// multiplication using logarithms
-(int)gMul:(int)a:(int)b
{
return(((a==0)||(b==0))?0:(gExp[gLog[a]+gLog]));
}

-(int)gInv:(int)a
{
return(gExp[TABLESIZE-1-gLog[a]]);
}

// From Cain, Clark, "Error-Correction Coding For Digital Communications", pp. 216.
-(void)modifiedBerlekampMassey
{
register int i,n;
int L,L2,k,d;
int *psi,*psi2,*D,*gamma;

if((psi=(int *)malloc(sizeof(int)*maxdeg))==NULL){
return;
}
if((psi2=(int *)malloc(sizeof(int)*maxdeg))==NULL){
return;
}
if((D=(int *)malloc(sizeof(int)*maxdeg))==NULL){
return;
}
if((gamma=(int *)malloc(sizeof(int)*maxdeg))==NULL){
return;
}

// initialize Gamma, the erasure locator polynomial
[self initGamma:gamma];

// initialize to z
[self copyPoly:D:gamma];
[self mulzPoly:D];

[self copyPoly:psi:gamma];

k=-1;
L=NErasures;

for(n=NErasures;n<npar;n++){
d=[self computeDiscrepancy:psi:synBytes:L:n];
if(d!=0){
// psi2 = psi - d*D
for(i=0;i<maxdeg;i++){
psi2=psi^[self gMul:d:D];
}

if(L<(n-k)){
L2=n-k;
k=n-L;
// D = scalePoly(gInv(d), psi);
for(i=0;i<maxdeg;i++){
D=[self gMul:psi:[self gInv:d]];
}
L=L2;
}

memcpy(psi,psi2,maxdeg*sizeof(int));
}
[self mulzPoly:D];
}

memcpy(Lambda,psi,maxdeg*sizeof(int));

[self computeModifiedOmega];

free(psi);
free(psi2);
free(D);
free(gamma);
}

// given Psi (called Lambda in modifiedBerlekampMassey) and synBytes,
// compute the combined erasure/error evaluator polynomial as Psi*S mod z^4
-(void)computeModifiedOmega
{
int *product;

if((product=(int *)malloc(sizeof(int)*maxdeg*2))==NULL){
return;
}

[self mulPolys:product:Lambda:synBytes];
[self zeroPoly:Omega];

memcpy(Omega,product,npar*sizeof(int));
free(product);
}

/* polynomial multiplication */
-(void)mulPolys:(int *)dst:(int *)p1:(int *)p2
{
register int i,j;
int *tmp;

if((tmp=(int *)malloc(sizeof(int)*maxdeg*2))==NULL){
return;
}

memset(dst,0,maxdeg*2*sizeof(int));

for(i=0;i<maxdeg;i++){
memset((tmp+maxdeg),0,maxdeg*sizeof(int));
// scale tmp1 by p1
for(j=0;j<maxdeg;j++){
tmp[j]=[self gMul:p2[j]:p1];
}
// and mult (shift) tmp1 right by i
for(j=(maxdeg*2)-1;j>=i;j--){
tmp[j]=tmp[j-i];
}
memset(tmp,0,i*sizeof(int));
// add into partial product
for(j=0;j<(maxdeg*2);j++){
dst[j]^=tmp[j];
}
}
free(tmp);
}

// gamma = product (1-z*a^Ij) for erasure locs Ij
-(void)initGamma:(int *)gamma
{
register int i;
int *tmp;

if((tmp=(int *)malloc(sizeof(int)*maxdeg))==NULL){
return;
}

[self zeroPoly:gamma];
[self zeroPoly:tmp];

gamma[0]=1;

for(i=0;i<NErasures;i++){
[self copyPoly:tmp:gamma];
[self scalePoly:gExp[ErasureLocs]:tmp];
[self mulzPoly:tmp];
[self addPolys:gamma:tmp];
}
free(tmp);
}

-(void)computeNextOmega:(int)d:(int *)A:(int *)dst:(int *)src
{
register int i;

for(i=0;i<maxdeg;i++){
dst=src^[self gMul:d:A];
}
}

-(int)computeDiscrepancy:(int *)lambda:(int *)S:(int)L:(int)n
{
register int i,sum=0;

for(i=0;i<=L;i++){
sum^=[self gMul:lambda:S[n-i]];
}

return(sum);
}

// polynomial arithmetic
-(void)addPolys:(int *)dst:(int *)src
{
register int i;

for(i=0;i<maxdeg;i++){
dst^=src;
}
}

-(void)copyPoly:(int *)dst:(int *)src
{
memcpy(dst,src,maxdeg*sizeof(int));
}

-(void)scalePoly:(int)k:(int *)poly
{
register int i;

for(i=0;i<maxdeg;i++){
poly=[self gMul:k:poly];
}
}

-(void)zeroPoly:(int *)poly
{
memset(poly,0,maxdeg*sizeof(int));
}

// multiply by z, i.e., shift right by 1
-(void)mulzPoly:(int *)src
{
register int i;

for(i=maxdeg-1;i>0;i--){
src=src[i-1];
}
src[0]=0;
}

/* Finds all the roots of an error-locator polynomial with coefficients
* Lambda[j] by evaluating Lambda at successive values of alpha.
*
* This can be tested with the decoder's equations case.
*/

-(void)findRoots
{
int sum;
register int i,j;

NErrors=0;

for(i=1;i<TABLESIZE;i++){
sum=0;
// evaluate lambda at i
for(j=0;j<npar+1;j++){
sum^=[self gMul:gExp[(i*j)%(TABLESIZE-1)]:Lambda[j]];
}
if(sum==0){
ErrorLocs[NErrors]=(TABLESIZE-1-i);
NErrors++;
#ifdef DEBUG
fprintf(stderr,"Root found at i = %d, (255-i) = %d\n",i,(TABLESIZE-1-i));
#endif
}
}
}

/* Combined Erasure And Error Magnitude Computation
*
* Pass in the codeword, its size in bytes, as well as
* an array of any known erasure locations, along the number
* of these erasures.
*
* Evaluate Omega(actually Psi)/Lambda' at the roots
* alpha^(-i) for error locs i.
*
* Returns 1 if everything ok, or 0 if an out-of-bounds error is found
*
*/

-(int)correctErrorsErasures:(unsigned char *)codeword:(int)csize:(int)nerasures:(int *)erasures
{
int r,i,j,err;
int num,denom;

// If you want to take advantage of erasure correction, be sure to
// set NErasures and ErasureLocs[] with the locations of erasures.

NErasures=nerasures;

memcpy(ErasureLocs,erasures,NErasures);

[self modifiedBerlekampMassey];
[self findRoots];

if((NErrors<=npar)&&(NErrors>0)){
// first check for illegal error locs
for(r=0;r<NErrors;r++) {
if(ErrorLocs[r]>=csize){
#ifdef DEBUG
fprintf(stderr,"Error loc i=%d outside of codeword length %d\n",i,csize);
#endif
return(0);
}
}

for(r=0;r<NErrors;r++){
i=ErrorLocs[r];
// evaluate Omega at alpha^(-i)
num=0;
for(j=0;j<maxdeg;j++){
num^=[self gMul:Omega[j]:gExp[((TABLESIZE-1-i)*j)%(TABLESIZE-1)]];
}
// evaluate Lambda' (derivative) at alpha^(-i) ; all odd powers disappear
denom=0;
for(j=1;j<maxdeg;j+=2){
denom^=[self gMul:Lambda[j]:gExp[((TABLESIZE-1-i)*(j-1))%(TABLESIZE-1)]];
}

err=[self gMul:num:[self gInv:denom]];
#ifdef DEBUG
fprintf(stderr,"Error magnitude %#x at loc %d\n",err,csize-i);
#endif
codeword[csize-i-1]^=err;
}
return(1);
}else{
#ifdef DEBUG
if(NErrors){
fprintf(stderr,"Uncorrectable codeword\n");
}
#endif
return(0);
}
}

// models crc hardware (minor variation on polynomial division algorithm)
-(short int)crcHWare:(short int)data:(short int)genpoly:(short int)accum
{
register short int i;

data<<=8;

for(i=8;i>0;i--){
if((data^accum)&0x8000){
accum=((accum<<1)^genpoly)&0xFFFF;
}else{
accum=(accum<<1)&0xFFFF;
}
data=(data<<1)&0xFFFF;
}
return(accum);
}

// Computes the CRC-CCITT checksum on array of byte data, length len
-(short int)crcCCITT:(unsigned char *)msg:(int)len
{
register int i;
register short int acc=0;

for(i=0;i<len;i++){
acc=[self crcHWare:(short int)msg:(short int)0x1021:acc];
}
return(acc);
}

-(void)zeroFillFrom:(unsigned char *)buf:(int)from:(int)to
{
register int i;

for(i=from;i<to;i++){
buf=0;
}
}

// debugging routines
-(void)printParity
{
register int i;

printf("Parity Bytes: ");
for(i=0;i<npar;i++){
printf("[%d]:%x, ",i,pBytes);
}
printf("\n");
}

-(void)printSyndrome
{
register int i;

printf("Syndrome Bytes: ");
for(i=0;i<npar;i++){
printf("[%d]:%x, ",i,synBytes);
}
printf("\n");
}

// Append the parity bytes onto the end of the message
-(void)build_codeword:(unsigned char *)msg:(int)l:(unsigned char *)dst
{
register int i;

memcpy(dst,msg,l*sizeof(int));
for(i=0;i<npar;i++){
dst[i+l]=pBytes[npar-1-i];
}
}

/*
* Reed Solomon Decoder
*
* Computes the syndrome of a codeword. Puts the results
* into the synBytes[] array.
*/

-(void)deCode:(unsigned char *)data:(int)l
{
register int i,j;
int sum;

[self setLength:l];

for(j=0;j<npar;j++){
sum=0;
for(i=0;i<l;i++){
sum=data^[self gMul:gExp[j+1]:sum];
}
synBytes[j]=sum;
}
}

-(void)deCode:(unsigned char *)data
{
[self deCode:data:length];
}

-(void)deCode:(unsigned char *)data:(int)l:(int)n
{
[self setNPAR:n];
[self setLength:l];
[self deCode:data:length];
}

// Check if the syndrome is zero
-(int)checkSyndrome
{
register int i;
int nz=0;

for(i=0;i<npar;i++){
if(synBytes!=0){
nz=1;
break;
}
}
return nz;
}

-(void)debugCheckSyndrome
{
register int i;

for(i=0;i<3;i++){
printf(" inv log S[%d]/S[%d] = %d\n",i,i+1, \
gLog[[self gMul:synBytes:[self gInv:synBytes[i+1]]]]);
}
}

/* Create a generator polynomial for an n byte RS code.
* The coefficients are returned in the genPoly arg.
* Make sure that the genPoly array which is passed in is
* at least n+1 bytes long.
*/

-(void)computeGenPoly:(int)l:(int *)genpoly
{
register int i;
int *tp,*tp1;

if((tp=(int *)malloc(sizeof(int)*TABLESIZE))==NULL){
return;
}
if((tp1=(int *)malloc(sizeof(int)*TABLESIZE))==NULL){
return;
}

// multiply (x + a^n) for n = 1 to l
[self zeroPoly:tp1];
tp1[0]=1;

for(i=1;i<=l;i++){
[self zeroPoly:tp];
tp[0]=gExp; /* set up x+a^n */
tp[1]=1;

[self mulPolys:genpoly:tp:tp1];
[self copyPoly:tp1:genpoly];
}
free(tp);
free(tp1);
}

/* Simulate a LFSR with generator polynomial for n byte RS code.
* Pass in a pointer to the data array, and amount of data.
*
* The parity bytes are deposited into pBytes[], and the whole message
* and parity are copied to dest to make a codeword.
*
*/

-(void)enCode:(unsigned char *)msg:(int)l:(unsigned char *)dst
{
register int i,j;
int *LFSR,dbyte;

if((LFSR=(int *)malloc(sizeof(int)*(npar+1)))==NULL){
return;
}

memset(LFSR,0,npar*sizeof(int));

[self setLength:l];

for(i=0;i<l;i++){
dbyte=msg^LFSR[npar-1];

for(j=npar-1;j>0;j--){
LFSR[j]=LFSR[j-1]^[self gMul:genPoly[j]:dbyte];
}
LFSR[0]=[self gMul:genPoly[0]:dbyte];
}
memcpy(pBytes,LFSR,npar*sizeof(int));

[self build_codeword:msg:l:dst];

free(LFSR);
}

-(void)enCode:(unsigned char *)msg:(unsigned char *)dst
{
[self enCode:msg:length:dst];
}

-(void)enCode:(unsigned char *)msg:(int)l:(unsigned char *)dst:(int)n
{
[self setNPAR:n];
[self setLength:l];
[self enCode:msg:length:dst];
}

@end


測試程式
RSCode.m

// Created by Tasuka Hsu on 03/25/2010.
// Copyleft 2010 http://Tasuka.IDV.TW.
// Original C Source code is from http://rscode.sourceforge.net

#import <Foundation/Foundation.h>
#import "RSEncodeDecode.h"

#define ML (sizeof(msg)+NPAR)

// Introduce a byte error at LOC
void byte_err(int err,int loc,unsigned char *dst)
{
//printf("Adding Error at loc %d, data %#x\n",loc,dst[loc-1]);
dst[loc-1]^=err;
}

// Pass in location of error (first byte position is labeled starting at 1, not 0), and the codeword.
void byte_erasure(int loc,unsigned char *dst,int cwsize,int *erasures)
{
//printf("Erasure at loc %d, data %#x\n",loc,dst[loc-1]);
dst[loc-1]=0;
}

int main (int argc, const char * argv[]) {
NSAutoreleasePool *pool=[[NSAutoreleasePool alloc] init];

unsigned char msg[]="Learn from other people's mistakes, you do'nt have time to make your own.";
unsigned char codeword[TABLESIZE];

int erasures[16];
int nerasures=0;

// Initialize RSCode Encode Decode Object
RSEncodeDecode *RS=[[RSEncodeDecode alloc] init];

[RS setNPAR:17];
[RS setLength:sizeof(msg)];

// Encode data into codeword, adding NPAR parity bytes
//[RS enCode:msg:sizeof(msg):codeword];
[RS enCode:msg:codeword];

printf("Encoded data is: \"%s\"\n",codeword);

// Add errors and two erasures
byte_err(0x35,3,codeword);
byte_err(0x41,6,codeword);
byte_err(0x40,10,codeword);

byte_err(0x23,17,codeword);
byte_err(0x34,19,codeword);

byte_err(0x30,53,codeword);
byte_err(0x32,65,codeword);

printf("with some errors: \"%s\"\n",codeword);

// We need to indicate the position of the erasures.
// Eraseure positions are indexed (1 based) from the end of the message...
erasures[nerasures++]=ML-16;
erasures[nerasures++]=ML-54;

// Now decode -- encoded codeword size must be passed
[RS deCode:codeword:ML];

// check if syndrome is all zeros
if([RS checkSyndrome]!=0){
[RS correctErrorsErasures:codeword:ML:nerasures:erasures];
printf("Corrected codeword: \"%s\"\n",codeword);
}
// Release RSCode Encode Decode Object
[RS release];

[pool drain];
return 0;
}

發表回應 發表回應 ( 923預覽 )   |  [ 0 引用 ]   |  permalink   |   ( 3 / 360 )


<<開始 <前一頁 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 下一頁> 最後>>