Xun’s blog

从通用到专用

CPU-DSPs-FPGA-ASIC

与cpu相比dsp的好处是采用哈佛结构有更大的数据吞吐量和运算效率。

FPGA由于其可通过软件编程快速定制符合特定算法需要的硬件结构，可通过硬件并行来获取性能。

http://www.dspdesignline.com/showArticle.jhtml?articleID=196802403

总的来说DSP开发更简单快速，貌似FPGA更有前途。

http://delabs.googlepages.com/fpga-asic

FlashBurn通过CCS连接目标板的JTAG接口来和目标板通信。

FBTC(FlashBurn Target Component)是CCS生成的普通.out程序，FlashBurn接上目标板后首先把FBTC加载到目标板RAM。然后FBTC作为FlashBurn在目标板上的内应在DSP上运行并通过JTAG口把指定的.hex文件烧写到Flash上。

http://www.softwaredesignsolutions.com/flashburn_how.aspx

http://www.softwaredesignsolutions.com/flashburn_debug.aspx

GEL General Extension Language 是用来设置CCS和初始化开发板的一种解释性语言。

StartUp()ccs启动时运行。初始化ccs

OnTargetConnect 连接到开发板是运行.初始化开发板.

新版的CCS要通过Debug-Connect连接开发板,所以在startup初始化开发板会出错.

StartUp()
{
    setup_memory_map();

  //  GEL_Reset(); 
   // init_emif();

}

OnTargetConnect()

{

GEL_Reset(); 
init_emif();

}

合纵达DEC643

GEL_MapAdd(0×01800000, 0, 0×00000054, 1, 1); /* EMIFA CTL REGS */54改为58。

参考SPRAA74。

ssh-keygen生成密钥对。

服务器~/.ssh/authorized_keys存放公钥。

下载私钥到Windows客户端，用puttygen转换为ppk格式。

设置好putty后保存为一个新的session供以后使用，然后打开连接。

putty用保存的私钥和服务器上ssh默认的22端口通信，认证成功后，服务器会分配一个tty给putty。具体可通过echo $SSH_TTY查看。

远程X

在本地Windows上运行CygwinX，在随之启动的xterm中用xhost + ip允许远程访问。

putty到远程主机，export DISPLAY=ip:0.0 定位远程X server，并运行x client程序。

ssh的端口转发

比如我想访问一台装了ssh和apache的服务器的web服务。

一种方法是直接在浏览器中输入服务器地址，但通讯过程中的所有信息都是明文的（http）。

也可以通过ssh转发来加密，方法是（对于Windows，Linux可以直接使用ssh client）

运行PLINK.EXE  -L 80:127.0.0.1:80  serverip -i path2ppk

plink建立了一个把本地端口80转发到服务器端口80的转发。

现在一个新的访问模式是：打开浏览器输入127.0.0.1，浏览器把web请求报文发给本地80端口（由plink控制），plink把报文加密以后发给远程ssh服务器，远程ssh服务器把从22端口接收的加密报文解密后转发给80端口，然后用同样的方式处理apache的响应。

整个加密过程是透明的，浏览器以为自己在和一台本地web服务器通讯。apache以为自己在为一个本地的客户端提供服务。但其实他们在两台不同的电脑上面，而这两台电脑通过ssh加密了所有的通讯。

Cygwin安装OpenSSH

chmod +r  /etc/passwd
chmod +r  /etc/group
chmod  777  /var
ssh-host-config  -y

net start sshd
or
cygrunsrv  –start  sshd

用Publickey加固ssh

1.在本机上用ssh-keygen生成rsa密钥对。

2.把其中的公钥导入远程机器的/home/usr/.ssh/authorized_keys

3.ssh usr@serverip 访问。

详细步骤：

1.在本机运行ssh-keygen生成密钥对。密钥默认放在~/.ssh目录，pub结尾的是公钥。

2.scp id_rsa.pub usr@serverip:  复制公钥到远程帐号主目录下，注意结尾的冒号。

   ssh usr@serverip 输入密码登录服务器，因为publickey还没有部署好这里使用密码方式访问ssh，之后可在服务器端的/etc/ssh/sshd_config禁止密码方式登录。

登录以后：

cat id_dsa.pub >> ~/.ssh/authorized_keys
rm  id_dsa.pub
退出。

3.ssh usr@serverip 自动用publickey方式访问。

如果出现Permissions  for .ssh/id_dsa are too open.这样的错误用chmod go-wrx ~/.ssh 更改一下.ssh目录权限。其他一些莫名其妙的问题请用-v开关输出ssh连接过程的详细信息以供检查。

最后发现Cygwin+ssh+Terminator比putty好用。

Windows窗口的右上角除了最小化，最大化，关闭之外还应该有一个保持前端显示的按钮，这一点Gnome就很好。

搜了一下这类小工具，

http://www.softpedia.com/downloadTag/Always+On+Top

勉强就用deskpins了。

ssh后vim出错。

E558: Terminal entry not found in terminfo
'terminator' not known. Available builtin terminals are:
    builtin_riscos

…………

解决方法：

把本地的~/.terminfo/t/terminator拷贝一份到远程主机的相同目录。

http://software.jessies.org/terminator/faq.html

安装Fedora

有1G以上U盘的话推荐下载live cd后用liveusb-creator安装，即环保又快速。

LAMP环境搭建

apache
yum install httpd
chkconfig httpd on
service httpd start
–设置iptable开放80端口。 

mysql
yum install mysql mysql-server
chkconfig  mysqld on
service mysqld start

PHP
yum install php php-mysql
service httpd restart 

http://fedorasolved.org/server-solutions/lamp-stack

DVDiso设为yum源

如果网络不好可以通过Fedora的DVD ISO建立本地yum源。

mount ISO到/mnt/repo

sudo vi /etc/yum.repos.d/fedora.repo

注释掉[fedora]的baseurl，并加上

baseurl=file:///mnt/repo
ZZ退出
sudo yum update
如果提示有其他进程holding yum lock的话，把自动更新关了。
sudo vi /etc/yum.repos.d/fedora-updates.repo 修改enbale值为0

安装WordPress

数据库准备

mysqladmin -u root password ‘new-password’  #创建密码，mysql默认root空密码

mysqladmin -u root –p create wordpress     #创建名为wordpress的数据库

把wordpress解压后丢到一个apache找得到的地方，如/var/www/html/wordpress，当然也可以自己在httpd.conf里建一个Alias链到其他目录。

sudo chown -R apache:apache /var/www/html/wordpress #修改owner为apache。

修改wp-config-sample.php填上数据库信息，保存为wp-confg.php 。

设置无误的话现在就可以通过浏览器访问了。

作为服务器的话没有必要开X。

修改启动默认runlevel
vi /etc/inittab把default runlevel  从5改为3。

Fedora的Runlevels
0 - halt (Do NOT set initdefault to this)
1 - Single user mode
2 - Multiuser, without NFS (The same as 3, if you do not have networking)
3 - Full multiuser mode
4 - unused or Admin
5 - X11
6 - reboot (Do NOT set initdefault to this)

启动时临时修改runlevel

进入grub菜单，修改kernel行在末尾加一数字。

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

int euler4()
{
       int max=0;
       for(int i=999;i>99;i–)
           for(int j=999;j>99;j–)
         {
             int n=i*j;
             int a6=n/100000;
             int a5=(n/10000)%10;
             int a4=(n/1000)%10;
             int a3=(n/100)%10;
             int a2=(n/10)%10;
             int a1=n%10;
             if(a6==a1&&a5==a2&&a4==a3)
             {
                 if(n>max)
                     max=n;
             }
        }    
         return max;
}

 

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

int euler5()
{
     int n=20;   
     while(true)
     {
     bool flag=true;
     for(int i=2;i<21;i+=1)
     {
         if(n%i!=0)
         {
             flag=false;
             break;
         }
     }
     if(flag)return n;
     n++;
     }    
}

Problem 6

14 December 2001

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

int euler6()
{
     int n1=0,n2=0;
        for(int i=1;i<=100;i++)
        {
            n1+=i;
            n2+=i*i;
        }
        return n1*n1-n2;
}

Project Euler的第三题。

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

当时马上写下的代码是

_int64 euler3(_int64  n)
{
    for(_int64 i=n-1;i>1;i–)
    {
        if(IsPrime(i))
            if(n%i==0) 
               return i; 
    }
    return 1;
}

inline bool IsPrime(_int64 num)
{
    for(_int64 i=2;i<num;i++) {
        if(num%i==0) {
            return false;
        }
    }
    return true;
}

结果程序在我1.86G双核CPU上跑了20多个小时未果，汗一个。

仔细数了一下600851475143的位数发现是个千亿级的数字，而我用这个N^2复杂度加大量取模运算的算法显然是力不从心。

因为之前学过一点数论，突然意识到这个问题其实就是经典的大数分解问题。手边正好有一本Schneier的应用密码学，于是复习了一点数论知识。

因子分解目前最新的算法是数域筛选法，而分解110位以内的十进制数最快的方法是二次筛选法，而且二次筛选法相对要简单很多。

开始之前，首先要对素数怀有一种崇敬的心情，因为它不仅是RSA加密算法的基础，也是整个数学的基础，所有的数都可以表示为一些素数的乘积形式，而且这种表示是唯一的，那些只能表示成1乘以自身的数才是素数。

费马的方法

要分解N，如果能找到a，b使得a^2-b^2=N，那么N就能分解成（a-b)(a+b)，于是问题就转化成测试不同的a，使得a^2-N等于某数的平方。

a可以从sqrt（N）开始取，然后不停的加一，直到找到某个a^2-N=S^2。费马的方法之所以可行是因为a^2-N相对于N来说是一个很小的数（至少在开始的时候）。

这种方法的缺点是在碰到S^2之前要测试很多a^2-N，因为平方数不那么容易碰到。一种改进是把得到的a^2-N序列中的数相乘，看能不能更快的得到一个平方数。因为如果

（a1^2-N）（a2^2-N）=S^2，设A=a1*a2

A^2-S^2=N(N-a1^2-a2^2)=(A-S)(A+S)

这样(A-S)和(A+S)中必有一个同N有公因子，然后就可以用欧几里德算法很快得找出这个因子。

a^2-N序列中的数相乘很容易得到一个非常大的数，这好像会带来很大的运算量，但这种方法可行是因为有一种方法可以快速的判断多个数相乘后的结果是否为平方。

因为任何数都有一种唯一的素因子分解形式，一个数是否为平方，取决于它的素因子能否等分为两份，即所有的素因子的指数为偶数。据此我们可以以素数为列，根据每个数的素因子存在情况建立矩阵，不存在或指数为偶数的取零，指数为奇数的取一（因为我们只需要判断两个数相乘，也就是矩阵的行相加后各素数指数的奇偶性），这会涉及到对这些书的素数分解，但因为他们相对于最终要分解的数很小，难度也会小很多。但是要注意挑那些最大素因子比较小的数，这样可以控制矩阵列数的大小。对于最大素因子有一种叫B-smooth提法，也就是说最大素因子不大于B的数都是B-smooth的。

事实上随着需分解的数增大，这个算法的瓶颈在于从a^2-N序列中找出素因子小的数。这时候会用到数论中的二次剩余理论来筛选出这些数，这也是这个算法的命名由来。

二次剩余的定义：如果存在a使得a^2-N=kp（p是素数）则N是模p二次剩余。

注意到需要筛选数列正是计算a^2-N得到的，因此如果N不是模p二次剩余，p就不会是这个序列中的数的因子，（否则（a^2-N）%p=0）。

而判断N是否是模p剩余有一个快速的方法：计算N^(p-1)/2 % p 是否等于1。

于是我们可以设定一个阀值素数P，然后找出所有小于P并使N二次剩余的素数，用这些素数和他们的幂次方去除a^2-N序列，最后序列中等于1的那些数就都是P-smooth的了，用这些筛选出的P-smooth的数和小于P并使N二次剩余的素数序列构建平方判断矩阵，来寻找相乘造成平方的数的运算量就大大降低了。

编程的时候发现对于千亿级别的数，费马的方法就可以轻松解决了。

/*判断n是否是平方*/

bool quad(_int64 n)
{
    _int64 sqr=sqrt(double(n));
    if(sqr*sqr==n)
        return true;
    else return false;
}

/*素数判断是一个很大的话题，这里用的是最野蛮的方法*/

bool IsPrime(_int64 num)
{
    for(_int64 i=2;i<num;i++) {
        if(num%i==0) {
            return false;
        }
    }
    return true;
}

_int64 fermat(_int64 n)
{
    _int64 fac1,fac2,s;
    _int64 a=sqrt(double(n))+1;
    while(true)
    {
        s=pow(double(a),2)-n;
        if(quad(_int64(s)))
        {
            fac1=a-sqrt(double(s));
            fac2=a+sqrt(double(s));
            if(IsPrime(fac1))
            {
                cout<<"The factor is "<<fac1<<endl;
                return n;
            }
            else
            {
                fermat(fac1);
            }
            if(IsPrime(fac2))
            {
                cout<<"The factor is "<<fac2<<endl;
                return n;
            }
            else
            {
                fermat(fac2);
            }               
        }
        a++;
    }

在main函数里用time计了一下时，一共用了十秒，于是草草收工。

http://blogs.msdn.com/devdev/archive/2006/06/19/637332.aspx
http://en.wikipedia.org/wiki/Quadratic_sieve
http://www.boo.net/~jasonp/qs.html

显然这不是一个创造欧拉的工程，做做题而已，一想到欧拉几百年前就懂了我现在还不明白的东西就比较汗颜。

http://projecteuler.net

第一题

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

static int  Euler(int max)
{
    int mul5 = (max - 1) / 5;
    int mul3 = (max - 1) / 3;
    int mul15 = (max - 1) / 15;
    int sum=0;
    sum =  (1 + mul5)*mul5 / 2 * 5;
    sum += (1 + mul3)*mul3 / 2 * 3;
    sum -= (1 + mul15)*mul15 / 2 * 15;
     return sum;
}

第二题

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

static int  Euler(int max)
{
    int i = 1, j = 2, sum = 2, count = 0, tem = 0;
    while (j <= max)
    {
        tem = i;
         i = j;
        j = tem + j;
        count += 1;
        if (count == 3)
        {
            sum += j;
            count = 0;
        }
    }
    return sum; 
}

只有奇数加奇数才能得到偶数，所以偶数的出现稳定在3次一个循环，引入count来避免使用偶数判断运算。