精华内容
下载资源
问答
  • 哈夫曼树与哈夫曼编码代码实现

    千次阅读 多人点赞 2020-03-18 12:43:30
    有损压缩——压缩过程会丢失数据的部分信息,如压缩BMP位图为JPEG会导致精度损失 编码类型 定长编码方案:每个字符的编码长度一样,如ASCII码,128个字符,都是用8位二进制码表示的,最高位...

    数据压缩

    含义
    通过对数据重新的编码,减少数据占用的空间存储;使用的时候再进行解压缩,恢复数据的原有特性。
    类别

    1. 无损压缩——压缩过程没有数据丢失,解压得到原有数据特性。
    2. 有损压缩——压缩过程会丢失数据的部分信息,如压缩BMP位图为JPEG会导致精度损失

    编码类型

    1. 定长编码方案:每个字符的编码长度一样,如ASCII码,128个字符,都是用8位二进制码表示的,最高位为0,每个字符的编码与频率无关;
    2. 变长编码方案:每个字符的编码长度与其出现的频率有关,出现的频率越高,其二进制编码的长度越越短;频率越低,则二进制编码长度越长;
      最后总数据的编码长度最短,实现压缩数据。

    哈夫曼编码就是一种无损压缩方法,一种变长编码方案

    哈夫曼编码

    我们这里使用例子来演示
    现在存在字符串,长度15,各个字符及频率:A7,B5,C1,D2

    AAAABBBCDDBBAAA
    

    需要我们进行二进制编码,明显
    采用ASCII码编码,15个字符15字节,编码的长度为 15*8=120位

    使用哈夫曼编码
    1.我们先得到字符出现的频率集合(也叫权重集合),按从小到大排序

    {1257}
    

    2.构造哈夫曼树
    规则就是
    1.在频率集合中找出字符中最小的两个;小的在左边,大的在右边;这两个兄弟组成二叉树。他们的双亲为他们的频率(权值)之和。
    2.在频率表中删除此次找到的两个数,并加入此次最小两个数的频率和(把他们的双亲加入,然后排序)。

    在这里插入图片描述
    第一步,C1,D2最小 我们将其合成N3,3=1+2,得到的频率排序后的表为

    {357}
    

    在这里插入图片描述
    第二步,重复第一步,N3和B5合成N8,8=3+5我们将得到频率排序后的表为

    {78}
    

    在这里插入图片描述
    第三步,重复第一步,A7和N8合成N15,15=7+8我们将得到频率排序后的表为

    {15}
    

    此时只剩下一个数,我们就结束构造了。

    然后
    开始哈夫曼编码,左子树为边值0,右子树边值为1,代码里面我们是使用数组保存的
    我们得到的哈夫曼树为
    在这里插入图片描述
    得到的哈夫曼编码为(从根结点往下面叶子结点看)

    元素 编码
    A 0
    B 11
    C 100
    D 101

    所以我们最后的字串编码为 00001111111001011011111000,长度26位
    对比ASCII编码,压缩比为 120:26

    此时,我们传送任何由ABCD构成的字串,压缩与解压缩都是按照这个编码
    我们可以发现,哈夫曼编码得到的编码长度不一,而且,任何一个字符的编码都不是另一字符的编码前缀,所以不会导致识别错,保证了译码的唯一性。

    原因 我们这里约定了小的是左子树,大的是右子树,保证了哈夫曼树的唯一性,而且我们的编码元素都是处在叶子结点,结合树的一对多的关系我们就能知道每一个字符的编码唯一,不是其余字符编码的前缀

    哈夫曼树

    一些二叉树的概念

    1. 路径长度
      从结点X到结点Y的所经过的结点序列叫做从X到Y的一条路径,路径的边数叫做路径长度。从根结点到其余结点的路径长度之和叫做该二叉树的路径长度(Path Length),简称PL。
      n个结点的完全二叉树的路径长度最短,长度最短的又不仅仅是完全二叉树。
    2. 外路径长度
      从根结点到所有的叶子结点的路径长度之和为二叉树的外路径长度
    3. 带权路径长度
      因为字符的权值,即出现是频率不同,所有我们使用带权的二叉树来编码,根到X结点的带权路径长度就是从根结点到X结点的路径长度与X结点的权值的乘积,**二叉树的带权外路径长度就是所有的叶子结点的带权路径长度之和(Weight external Path Length)**简称WPL。

    哈夫曼树的定义
    就是同结点个数的所有的二叉树中,WPL最小的二叉树,HuffmanTree,也叫最优二叉树所以哈夫曼树不一定是唯一的!
    如图,四棵树的WPL都是26.
    在这里插入图片描述
    要想得到唯一一颗哈夫曼树,就要约束左右子树
    哈夫曼树构建的约束规则就是:合并结点时,权值较小的结点是左孩子,权值较大的是右孩子。

    代码演示

    我们现在对ABCDEFGH编码,使用三叉静态链表实现。
    1.构建哈夫曼树

    //定义哈夫曼树的结构
    typedef struct {
    	int data;//data域存储权值
    	int parent,lchild,rchild;//双亲与孩子
    } HTNode,*HuffmanTree;
    
    /*typedef struct{
    	string<char> str;
    
    }HuffmanTreenode,*HuffmancodeTree;*/
    //哈夫曼树的初始化 
    int InitHuffmanTree(HuffmanTree H,int weight,int parent,int lchild,int rchild)
    {
    	//HT = (HuffmanTree)malloc(n*sizeof(HTNode));//空间分配_我们通过createHuffmanTree来调用,无须分配
    	H->lchild=lchild;
    	H->rchild=rchild;
    	H->parent =parent;
    	H->data = weight;
    }
    
    //建立哈夫曼树!
    void CreateHuffmanTree(HuffmanTree &HT,int n,int *W)
    {
    	//叶子结点的初始化,相当于n棵树,每颗树只有一个结点,那么最后构造过程总的结点个数为:2*n-1 
    	//n-1+n = 2*n-1 
    
    	HT = (HuffmanTree)malloc((2*n-1)*sizeof(HTNode));//n个叶子结点的哈夫曼树结点是2n-1;
    	for(int i=0; i<n; i++) {
    		InitHuffmanTree(HT+i,W[i],-1,-1,-1);//初始化-1 
    	}
    	//开始寻找最小的两个叶子结点,构造哈夫曼树
    	for(int i=n; i<2*n-1; i++) { //我们构造n-1个度为2的结点
    		int min1=65522,min2=min1;//这里的两个数分别代表第一小,第二小
    		int x1=-1,x2=-1;//用来记录下标
    		for(int j=0; j<i; j++) {
    			if((HT+j)->parent==-1)//表示叶子结点没有父母
    				if((HT+j)->data<min1) {
    					min2=min1;
    					min1=(HT+j)->data;
    					x2=x1;
    					x1=j;
    				} else if((HT+j)->data<min2) {
    					min2=(HT+j)->data;
    					x2=j;
    
    				}
    		}
    		//合并两个叶子,让他们有同一个双亲
    		(HT+x1)->parent =i;
    		(HT+x2)->parent =i;
    		//然后我们让HT[i]指向这两个孩子,为了后来的逆序哈夫曼编码
    
    		InitHuffmanTree(HT+i,min2+min1,-1,x1,x2) ;//父结点构造 
    	}
    }
    //完成哈夫曼树的生成;
    

    2.哈夫曼树的编码

    //获得哈夫曼编码,n是指叶子个数,path是我们要获得的字符的编码 
    void HuffmanTreeCode(HuffmanTree HT,char *str,int n,int path,int &e)
    {
    	int i=0,j=0,m=0;
    	int child =path;//假设我们现在在叶子结点为child索引的地方,如1
    
    	int parent = (HT+child)->parent;//获取第一个叶子结点的父节点 的值 
    	//printf("leafe node is:%d \n",(HT+child)->data);
    
    	//开始逆序寻找根节点,及生成编码
    	for(i=n-1; parent!=-1; i--)  //当前结点不是根结点 ,逆序
    		if((HT+parent)->lchild==child) { //他的双亲指向的左孩子是不是我们当前遍历的这个叶子
    			str[j++] = '0';
    			child = parent;///此时parent!=-1 ,表示还有父节点 
    			parent=(HT+child)->parent;
    		} else {
    			str[j++] = '1';//实现编码
    			child = parent;
    			parent=(HT+child)->parent;
    		}
    	e=j;//表示一个叶子结点的编码结束
    
    }//一次获取一个字符的编码,时间复杂度为O(n)
    
    

    过程类似如图(借图):在这里插入图片描述
    3.打印所有的字符的编码

    for(int k=0; k<n; k++) {
    		HuffmanTreeCode(HT,str,n,k,e) ;
    		for(int j=e-1;j>=0 ; j--)
    			printf("%c ",str[j]);
    		printf("\n\n");
    	}
    

    上图:
    在这里插入图片描述
    在这里插入图片描述
    源代码

    #include "stdio.h"
    #include "malloc.h"
    #include "string.h"
    #include "string"
    
    //定义哈曼夫树的结构
    typedef struct {
    	int data;//data域存储权值
    	int parent,lchild,rchild;//双亲与孩子
    } HTNode,*HuffmanTree;
    
    /*typedef struct{
    	string<char> str;
    
    }HuffmanTreenode,*HuffmancodeTree;*/
    //哈曼夫树的初始化 
    void InitHuffmanTree(HuffmanTree H,int weight,int parent,int lchild,int rchild)
    {
    	//HT = (HuffmanTree)malloc(n*sizeof(HTNode));//空间分配
    	H->lchild=lchild;
    	H->rchild=rchild;
    	H->parent =parent;
    	H->data = weight;
    }
    
    //建立哈夫曼树!
    void CreateHuffmanTree(HuffmanTree &HT,int n,int *W)
    {
    	//叶子结点的初始化,相当于n棵树,每颗树只有一个结点,那么最后构造过程总的结点个数为:2*n-1 
    	//n-1+n = 2*n-1 
    
    	HT = (HuffmanTree)malloc((2*n-1)*sizeof(HTNode));//n个叶子结点的哈夫曼树结点是2n-1;
    	for(int i=0; i<n; i++) {
    		InitHuffmanTree(HT+i,W[i],-1,-1,-1);//初始化-1 
    	}
    	//开始寻找最小的两个叶子结点,构造哈夫曼树
    	for(int i=n; i<2*n-1; i++) { //我们构造n-1个度为2的结点
    		int min1=65522,min2=min1;//这里的两个数分别代表第一小,第二小
    		int x1=-1,x2=-1;//用来记录下标
    		for(int j=0; j<i; j++) {
    			if((HT+j)->parent==-1)//表示叶子结点没有父母
    				if((HT+j)->data<min1) {
    					min2=min1;
    					min1=(HT+j)->data;
    					x2=x1;
    					x1=j;
    				} else if((HT+j)->data<min2) {
    					min2=(HT+j)->data;
    					x2=j;
    
    				}
    		}
    		//合并两个叶子,让他们有同一个双亲
    		(HT+x1)->parent =i;
    		(HT+x2)->parent =i;
    		//然后我们让HT[i]指向这两个孩子,为了后来的逆序哈夫曼编码
    
    		InitHuffmanTree(HT+i,min2+min1,-1,x1,x2) ;//父结点构造 
    	}
    }
    //完成哈夫曼树的生成;
    
    //获得哈夫曼编码,n是指叶子个数,path是我们要获得的字符的编码 
    void HuffmanTreeCode(HuffmanTree HT,char *str,int n,int path,int &e)
    {
    	int i=0,j=0,m=0;
    	int child =path;//假设我们现在在叶子结点为child索引的地方,如1
    
    	int parent = (HT+child)->parent;//获取第一个叶子结点的父节点 的值 
    	//printf("leafe node is:%d \n",(HT+child)->data);
    
    	//开始逆序寻找根节点,及生成编码
    	for(i=n-1; parent!=-1; i--)  //当前结点不是根结点 ,逆序
    		if((HT+parent)->lchild==child) { //他的双亲指向的左孩子是不是我们当前遍历的这个叶子
    			str[j++] = '0';
    			child = parent;///此时parent!=-1 ,表示还有父节点 
    			parent=(HT+child)->parent;
    		} else {
    			str[j++] = '1';//实现编码
    			child = parent;
    			parent=(HT+child)->parent;
    		}
    	e=j;//表示一个叶子结点的编码结束
    
    }
    
    
    int main()
    {
    	int i,n;
    	int *w,e;
    
    	HuffmanTree HT;
    	//printf("Node Number:");
    	scanf("%d",&n);  //权值个数
    	w=(int *)malloc(n*sizeof(int)); //权值数组
    	//printf("Input weights:");
    	for ( i=0; i<n; i++) //录入权值
    		scanf("%d",&w[i]);
    	CreateHuffmanTree(HT,n,w);
    	//printf("the first node is:%d\n",HT->data);
    	//printf("create sussessfully\n");
    
    	//定义一个数组存储哈夫曼编码
    	char str[n];
    	for(int k=0; k<n; k++) {
    		HuffmanTreeCode(HT,str,n,k,e) ;
    		for(int j=e-1;j>=0 ; j--)
    			printf("%c",str[j]);
    		printf("\n");
    	}
    	free(HT);
    	return 0;
    }//main
    
    展开全文
  • 其实刚开始我对编码与加密的概念区分的不是非常清楚,一度以为加密就是对信息进行编码,这是一种错误的观点。编码是将数据信息转化成一种固定格式的编码信息,而加密是为了保证信息传输的安全性,两者还是有区别的。...

    其实刚开始我对编码与加密的概念区分的不是非常清楚,一度以为加密就是对信息进行编码,这是一种错误的观点。编码是将数据信息转化成一种固定格式的编码信息,而加密是为了保证信息传输的安全性,两者还是有区别的。接下来就给大家讲讲编码与加密、解密。
    一,编码
    编码是为了方便不同系统间的信息传输,将数据转化成固定格式的信息,通过编码可以得到原始信息。常见的编码我们都已经很熟悉了,比如ASCII编码、URL编码、HTML实体编码以及Base编码等。
    1,ASCII编码
    ASCII编码大致可以分作三部分组成:
    第一部分是:ASCII非打印控制字符(参详ASCII码表中0-31);
    第二部分是:ASCII打印字符,也就是CTF中常用到的转换;
    第三部分是:扩展ASCII打印字符(详见 ASCII码表 二)。
    例:easy—101 97 115 121

    (ASCII表——来自百度百科)

    (ASCII码表 二)
    2,URL编码
    又叫百分号编码,是统一资源定位编码方式。URL 地址(常说网址) 规定了常用地数字,字母可以直接使用,另外一批作为特殊用户字符也可以直接用(/,:@等),剩下的其它所有字符必须通过%xx 编码处理。编码方法很简单,在该字节 ascii 码的的 16 进制字符前面加%. 如空格字符,ascii 码是 32,对应16 进制是’20′,那么 urlencode 编码结果是:%20。
    例:https://baike.baidu.com/item/ABC
    URL转码: %68%74%74%70%73%3A%2F%2F%62%61%69%6B%65%2E%62%61%69%64%75%2E%63%6F%6D%2F%69%74%65%6D%2F%41%42%43
    3,HTML实体编码
    一些字符在 HTML 中是预留的,拥有特殊的含义,比如小于号‘<’用于定义 HTML 标签的开始。如果我们希望浏览器正确地显示这些字符,我们必须在 HTML 源码中插入字符实体。用一个编号写入HTML代码中来代替一个字符,在使用浏览器访问网页时会将这个编号解析还原为字符以供阅读。


    (来自http://www.w3school.com.cn/html/html_entities.asp
    例:easy——&#101;&#97;&#115;&#121
    4,Base编码
    Base家族主要有Base16、Base32、Base64。Base64由大小写字母和数字,+/组成(=号用作填充字符),Base32则是只有大写字母和234567。其中Base64/32是网络上最常见的用于传输8Bit字节代码的编码方式之一。Base64编码是从二进制到字符的过程,可用于在HTTP环境下传递较长的标识信息。例如,在Java Persistence系统Hibernate中,就采用了Base64来将一个较长的唯一标识符(一般为128-bit的UUID)编码为一个字符串,用作HTTP表单和HTTP GET URL中的参数。Base64编码保证了二进制数据的安全。


    例:Base64:easy—ZWFzeQ==
    (Base64的代码实现:https://baike.baidu.com/item/base64/8545775)
    5、Unicode编码
    Unicode编码有以下四种编码方式:
    源文本:The
    &#x [Hex]:The
    &# [Decimal]:The
    \U [Hex]:\U0054\U0068\U0065
    \U+ [Hex]:\U+0054\U+0068\U+0065
    6、莫尔斯电码(Morse Code)
    摩尔斯电码(又译为摩斯密码,Morse code)是一种时通时断的信号代码,通过不同的排列顺序来表达不同的英文字母、数字和标点符号。是早期的数字化通信形式,但是它不同于现代只使用零和一两种状态的二进制代码,它的代码包括五种:点、划、点和划之间的停顿、每个字符之间短的停顿、每个词之间中等的停顿以及句子之间长的停顿。
    除此之外,常用的编码方式还有敲击码(Tap code)等。编码在电子计算机、电视、遥控和通讯等方面广泛使用。编码是信息从一种形式或格式转换为另一种形式的过程;解码,是编码的逆过程。
    二、常见的代码混淆
    代码混淆(Obfuscated code)亦称花指令,是将计算机程序的代码,转换成一种功能上等价,但是难于阅读和理解的形式的行为。代码混淆可以用于程序源代码,也可以用于程序编译而成的中间代码。执行代码混淆的程序被称作代码混淆器。目前已经存在许多种功能各异的代码混淆器。常用的代码混淆有jsfuck、brainfuck,Vbscript.encode加密等
    1、Jsfuck
    jsfuck源于一门编程语言brainfuck,其主要的思想就是只使用8种特定的符号来编写代码。而jsfuck也是沿用了这个思想,它可以让你只用 6 个字符`[ ]( ) ! + `来编写 JavaScript 程序。此外,JSFuck可用于绕过恶意代码检测,且可以被用于跨站脚本攻击。因为缺乏原生JavaScript应有的特征,类似JSFuck的JavaScript混淆技术可帮助恶意代码绕过入侵防御系统或内容过滤器。现实中,因为JSFuck中缺少字母数字字符,且eBay中的内容过滤器曾存在缺陷,使得卖家曾经可以在他们的eBay拍卖页面中嵌入任意JSFuck脚本
    例:http://utf-8.jp/public/jsfuck.html
    2、Brainfuck
    Brainfuck是一种极小化的计算机语言,目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。BrainFuck 语言只有八种符号,所有的操作都由这八种符号(` > < + – . , [ ] `)的组合来完成。
    例:hello world
    +++++ +++++ [->++ +++++ +++<] >++++ .—. +++++ ++..+ ++.
    <+ +++++ ++[->----- ---<] >—- —– —– -.<++ +++++ ++[-> ++
    +++ ++++< ]>+++ +++.—— –.++ +.— —.- —– –.<
    在线解密工具: https://www.splitbrain.org/services/ook
    3、Vbscript.encode加密
    VBScript.encode是针对asp代码进行的一种加密混淆操作。
    样题: http://ctf5.shiyanbar.com:8080/aspencode/
    在线工具:http://adophper.com/encode.html
    4、Jjencode
    jjencode 将 JS 代码转换成只有符号的字符串,类似于 rrencode,介绍的,aaencode 可以将 JS 代码转换成常用的网络表情,也就是我们说的颜文字 js 加密。
    例: http://utf-8.jp/public/aaencode.html
    三、加密
    密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情报的,称为破译学,总称密码学。主要分为古典加密算法和现代密码学。
    1,古典加密算法
    古典密码算法曾经被广泛应用,大都比较简单,使用手工和机械操作来实现加密和解密。它的主要对象是文字信息,利用密码算法实现文字信息的加密和解密。古典密码编码方法归根结底主要有两种,即置换和代换。比较经典的有凯撒密码、栅栏密码、培根密码、仿射密码和维吉尼亚密码等。
    (1)凯撒密码
    是一种最简单且最广为人知的加密技术。它是一种替换加密的技术,明文中的所有字母按照按顺序进行 n 个字符错位转换后被替换成密文。
    例:ABCDE(偏移量为3)—DEFGH
    (2)栅栏密码
    把要加密的明文分成N个一组,然后把每组的第1个字连起来,形成一段无规律的话即为栅栏密码。
    例:明 文:The quick brown fox jumps over the lazy dog
    去空格:Thequickbrownfoxjumpsoverthelazydog
    分 组:Th eq ui ck br ow nf ox ju mp so ve rt he la zy do g
    密 文:Teucbonojmsvrhlzdghqikrwfxupoeteayo
    (3)培根密码
    又名倍康尼密码(英语:Bacon’s cipher)是由法兰西斯·培根发明的一种隐写术。是一种替换密码,每个明文字母被一个由5字符组成的序列替换。最初的加密方式就是由‘A’和’B'组成序列替换明文


    例:明文:THE DOG
    密文:baabb aabbb aabaa aaabb abbba aabba
    (4)仿射密码
    仿射密码(Affine Cipher)是一种单表代换密码,字母表中的每个字母相应的值使用一个简单的数学函数映射到对应的数值,再把对应数值转换成字母。每一个字母都是通过函数(ax + b)mod m加密,其中B是位移量,为了保证仿射密码的可逆性,a和m需要满足gcd(a , m)=1,一般m为设置为26。


    (5)维吉尼亚密码
    维吉尼亚密码(又译维热纳尔密码)是使用一系列凯撒密码组成密码字母表的加密算法,属于多表密码的一种简单形式。以其简单易用而著称,同时初学者通常难以破解,因而又被称为“不可破译的密码”。这也让很多人使用维吉尼亚密码来加密的目的就是为了将其破解。



    例:明文:THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
    密钥(循环使用,密钥越长相对破解难度越大):CULTURE
    加密过程:如果第一行为明文字母,第一列为密钥字母,那么明文字母’T'列和密钥字母’C'行的交点就是密文字母’V',以此类推。
    密文:VBP JOZGM VCHQE JQR UNGGW QPPK NYI NUKR XFK
    解密网站:https://www.qqxiuzi.cn/bianma/weijiniyamima.php
    2,现代密码学
    现代密码学研究信息从发端到收端的安全传输和安全存储,核心是密码编码学和密码分析学。1949年香农发表《保密系统的通信理论》标志着现代密码学的真正开始(第一次质的飞跃)。1976年,Diffie和Hellman发表《密码学的新方向》,标志着公钥密码体制的诞生(第二次质的飞跃)。
    现代密码学根据功能分为三类:
    ①、对称加密算法:DES,AES,RC4等。
    ②、公钥密码算法:RSA等
    ③、HASH函数:md5,sha1
    (1),对称加密算法
    在对称加密算法中,数据发信方将原始数据和加密密钥一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去,收信方需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文。在大多数的对称算法中,加密密钥和解密密钥是相同的,所以也称这种加密算法为秘密密钥算法或单密钥算法。它要求发送方和接收方在安全通信之前,商定一个密钥。对称算法的安全性依赖于密钥,泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密,所以密钥的保密性对通信的安全性至关重要。特点是算法公开、计算量小、加密速度快、加密效率高。
    对称加密的分类:流加密与分组加密
    * 流加密每次加密数据流的一位(bit)或者一个字节(byte)。如RC4。
    * 分组加密(通常也成为块加密)是将明文进行分组,加密算法对每个分组分别加密,通常明文分组和加密后得到的密文分组等长。典型的分组大小是64bit或128bit。如DES,3DES,AES。


    (2),HASH算法
    可直接音译为“哈希”,一般翻译为“散列”把任意长度的输入(又叫做预映射, pre-image),通过散列算法变换成固定长度的输出,该输出就是散列值。它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。
    常见HASH算法主要有MD5、SHA-1等。主要用于文件校验,数字签名,鉴权协议。另外这里还有一篇利用Hash碰撞而产生DOS攻击的案例,有兴趣的可以阅读一下:http://www.cnblogs.com/rush/archive/2012/02/05/2339037.html
    (其实把hash算法当成是一种加密算法,这是不准确的,我们知道加密总是相对于解密而言的,没有解密何谈加密呢,HASH的设计以无法解为目的的。并且如果我们不附加一个随机的salt值,HASH口令是很容易被字典攻击入侵的)
    (3),RSA算法
    RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用,是现今使用最广泛的公钥密码算法。和其它加密过程一样,对RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设Eve交给Bob一个公钥,并使Bob相信这是Alice的公钥,并且她可以截下Alice和Bob之间的信息传递,那么她可以将她自己的公钥传给Bob,Bob以为这是Alice的公钥。Eve可以将所有Bob传递给Alice的消息截下来,将这个消息用她自己的密钥解密,读这个消息,然后将这个消息再用Alice的公钥加密后传给Alice。理论上Alice和Bob都不会发现Eve在偷听他们的消息。今天人们一般用可靠的第三方机构签发证书来防止这样的攻击。根据密钥的使用方法,可以将密码分为对称密码和公钥密码。
    对称密码:加密和解密使用同一种密钥的方式
    公钥密码:加密和解密使用不同的密码的方式,因此公钥密码通常也称为非对称密码。
    RSA的加密过程可以使用一个通式来表达
    密文=明文^E mod N
    也就是说RSA加密是对明文的E次方后除以N后求余数的过程。
    从通式可知,只要知道E和N任何人都可以进行RSA加密了,所以说E、N是RSA加密的密钥,即E和N的组合就是公钥,用(E,N)来表示公钥。
    RSA的解密同样可以使用一个通式来表达
    明文=密文^D mod N
    即对密文进行D次方后除以N的余数就是明文,所以D和N的组合就是私钥,私钥=(D,N)



    RSA常见攻击方式
    ①、利用rsa加密流程求参数
    ②、分解N求私钥
    • 如果n的大小小于256bit,那么我们通过本地工具即可爆破成功。
    • 如果n在768bit或者更高,可以尝试使用一些在线的n分解网站,这些网站会存储一些已经分解成功的n,比如:http://factordb.com
    • 如果有多个n,可以尝试用求公约数的方式来求解两个N共同的素因子p,进而求解q
    • 在p,q的取值差异过大,或者p,q的取值过于相近的时候,Format方法与Pollard rho方法都可以很快将n分解成功。此类分解方法有一个开源项目yafu将其自动化实现了,不论n的大小,只要p和q存在相差过大或者过近时,都可以通过yafu很快地分解成功。
    ③、共模攻击
    如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密,那么就可以在不分解n的情况下还原出明文m的值。
    http://www.bystudent.com/?p=236 

    密码学在信息技术高速发展的当代具有很重要的意义,发展范围广且深。本文在写作过程中参考了许多资料,在此一并表示感谢。同时对于文章中涉及的知识只是粗略地简要介绍,如有不当之处还请指正。网上对密码学还有很多的资料,大家有兴趣的可以看一下。此外,文章中提到的各种解码及解密方式都可在这个网站中找到相应的工具(http://ctf.ssleye.com/

    **** 以下列出对于密码学学习很有帮助的参考资料 ****
    密码学 – 维基百科,自由的百科全书
    https://zh.wikipedia.org/zh-my/%E5%AF%86%E7%A0%81%E5%AD%A6
    CTF中那些脑洞大开的编码和加密 – DaBan – 博客园
    https://www.cnblogs.com/daban/p/5680451.html
    代码混淆的重要性
    https://www.jdon.com/50072
    密码学起源——由「凯撒加密」到「一次一密」
    https://baijiahao.baidu.com/s?id=1621013260155177917&wfr=spider&for=pc
    《现代密码学》 – WittPeng – 博客园
    https://www.cnblogs.com/WittPeng/p/8978737.html
    http://archive.keyllo.com/L-编程/Code-现代密码学—原理与协议.pdf
    http://archive.keyllo.com/L-%E7%BC%96%E7%A8%8B/Code-%E7%8E%B0%E4%BB%A3%E5%AF%86%E7%A0%81%E5%AD%A6%E2%
    80%94%E5%8E%9F%E7%90%86%E4%B8%8E%E5%8D%8F%E8%AE%AE.pdf

     

    展开全文
  • C++编码规范(1):代码注释

    万次阅读 2013-01-09 15:20:18
    C++编码规范(1):代码注释 C++编码规范(2):命名规范   当你阅读别人的代码时如果没有注释那会是件比较痛苦的事.一说到注释我们马上想到是通过//或/* */这样来添加一些描述信息.这只是狭义的注释. 广义的注释我们...

    C++编码规范(1):代码注释

    C++编码规范(2):命名规范

     

    当你阅读别人的代码时如果没有注释那会是件比较痛苦的事.一说到注释我们马上想到是通过//或/* */这样来添加一些描述信息.这只是狭义的注释.

    广义的注释我们可以理解为,任何有助于理解代码的信息都可以看成注释.

    我们可以把写代码和写文章类比下.自然语言会有词法,句法,语义这几个概念.代码中的语法和句法就相当于一个编程语言中的基本语法规范.这是我们学习一门编程语言必须掌握的.所以注释的时候一般不会涉及到这些信息.

    注释主要涉及到语义的描述.语义从大的方向,软件产品面向的应用来说,就是要解决的问题本身的逻辑,如果是些应用软件也可以叫业务逻辑.我们把业务逻辑理清头绪后就会来个啥数据建模之类的.然后写设计文档之类的,有啥概要设计与详细设计,这些文档可以看成非常重要的注释.

    然后就是写到代码里的注释了,通过//或/* */标识出来.还有一种注释叫自我注释,就是通过函数或变量名字就得得到一些有用的信息

     

    这里主要讲下用//或/* */做的注释

    用// 还是/* */就看你自己的偏好了.最重要的是保持一致,就是在一个项目中大家达成一致,全部用哪一种或者在某个地方用//,另外的地方用/* */

     

    注释的位置及常见内容

     

    1.文件注释

    在C++的代码都是分布在一个个的头文件和源文件中,如果是用的VS则是h后缀文件和cpp后缀文件. 当然了有时你用以内联函数还可能会有inl文件.每个文件的开头部分你可以添加注释信息.

    内容一般是:版权,作者,编写日期,功能描述.例如

    /**************************************************************************

    Copyright:MyCompany

    Author: Arwen

    Date:2013-01-09

    Description:Provide  functions  to connect Oracle

    **************************************************************************/

    或者

    //Copyright:MyCompany

    //Author: Arwen

    //Date:2013-01-09

    //Description:Provide functions to connect Oracle

     

    有时如果修改了代码,还可以添加修改人,日期,修改内容有目的这些信息.

     

    2.类注释

    一般是简单的说下这个类的功能,如果你在文件开头已经描述了这里也可以省略.如果要注释的话就可以这样简单的描述下.

    // COleDataObject -- simple wrapper for IDataObject

    class COleDataObject
    {

    }

    或者

    /*COleDataObject -- simple wrapper for IDataObject*/

     

    3.函数注释

    描述函数的功能及参数,其他相关信息.例如

    //Summary:  connect the database

    //Parameters:

    //       connInfo:A class contains the connect info ,such as user name ,pwd,etc.

    //       directConnect : use TNS name or use direct connection info

    //Return : true is connect successfully.

    bool ConnectDatabase(ConnectInfo connInfo, bool directConnect);

     

    或者

    /*

    *Summary: connect the database

    *Parameters:

    *     connInfo:A class contains the connect info ,such as user name ,pwd,etc.*    

    *     directConnect : use TNS name or use direct connection info

    *Return : true is connect successfully.

    */

     

     

    4.变量注释

    一个变量如果代表的意思不容易从变量名看出来,而且又挺重要的话最好也加点注释.例如

    UINT m_nGrowBy;     // number of cache elements to grow by for new allocs

    或者

    UINT m_nGrowBy;     /* number of cache elements to grow by for new allocs*/

     

    5.实现注释

    在一些逻辑性很强,不容易理解的代码块前添加注释.特别是是像一些算法,看起来就几行,但想个半天都未必明白到底是啥意思来着.

    例如

    // copy elements into the empty space
     while (nCount--)
          m_pData[nIndex++] = newElement;

    还有就是如果想针对函数的某些个参数做些注释,那最好把参数分几行写.

    void MyFunction(string name, //This is my name

                             int age)

     

    另外有时一个函数很长,里面有奶多个大括号{ } ,这样一嵌套,有时你不知道谁对应谁了,你要往里面插入代码就容易出错.你也可以在些结尾的大括号加个注释,表明它是哪个if或while语句的结束处.

    在C#中是可以通过#region 加 #endregion 来做注释.同时开发环境VS能提供支持让你方便的折叠这样注释的代码.

    VS也支持在C++中通过#pragma region 与 #pragma endregion 来做注释,但这在其它编译器中不会被识别,所以需要考虑到跨平台的话或者会使用不同的编译器的话就最好别用.

     

    6.TODO 注释

    todo的意思就是待做的事.比如你代码写了一半,然后下班了.为了方便你第二天很快的找到那具体地方,或者防止你忘记.就可以用todo注释下.因为一些开发环境提供了对它的支持,可以让你方便的找到哪些个地方有todo注释,起个书签的作用.你选View-->Task List,然后在下面的下拉列表中选择comments就会列出所有TODO注释信息.

    另外你也可以写个TODO留着以后实现那功能也行,注释信息一般可以写上你的名字和邮箱,然后说下待实现的功能或其他事项

    展开全文
  • HM编码代码阅读(29)——码率控制

    千次阅读 2017-02-14 11:38:51
    码率控制也叫速率控制,主要是控制编码后的比特率。 存在码率控制模块的原因是,有时候解码器处理的速度不够快、网络带宽不行 这些情况的存在要求我们必须减少数据的发送量(即比特率要变小),减少数据的发送量 ...

    码率控制


    介绍

    码率控制
        码率控制也叫速率控制,主要是控制编码后的比特率。
        存在码率控制模块的原因是,有时候解码器处理的速度不够快、网络带宽不行,这些情况的存在要求我们必须减少数据的发送量(即比特率要变小),减少数据的发送量
    意味着我们要对数据进行更近一步的压缩,在编码器中就表现为量化参数QP的变化。
        当满足一定码率要求的情况下,我们还需要让编码的失真尽量小。
        码率控制的核心就是要确定量化参数QP。

        如果不使用码率控制,那么量化参数QP就是自定义的或者根据需要选择


        码率控制是一级一级进行控制的,先分配图像组级(GOP)的比特数,然后分配图像级的比特数,再分配CTU级别的比特数。利用已经分配的比特数来确定量化参数。
        更多的细节请参考http://blog.csdn.net/nb_vol_1/article/details/53288902

    码率控制在HEVC中的实现


    码率控制流程

    在TEncCfg中有个布尔类型的m_RCEnableRateControl成员,它表示是否使用码率控制
    在HM中码率控制的流程是:

        1、在TEncTop::create中,定义了编码序列级别的码率控制

    	if ( m_RCEnableRateControl )
    	{
    		// 码率控制器初始化
    		m_cRateCtrl.init( m_framesToBeEncoded, m_RCTargetBitrate, m_iFrameRate, m_iGOPSize, m_iSourceWidth, m_iSourceHeight,
    			g_uiMaxCUWidth, g_uiMaxCUHeight, m_RCKeepHierarchicalBit, m_RCUseLCUSeparateModel, m_GOPList );
    	}
        2、在TEncTop::encode中,定义了图像组级别的码率控制

    	if ( m_RCEnableRateControl )
    	{
    		m_cRateCtrl.initRCGOP( m_iNumPicRcvd );
    	}
    	if ( m_RCEnableRateControl )
    	{
    		m_cRateCtrl.destroyRCGOP();
    	}

        3、在TEncGOP::compressGOP,定义了图像级别的码率控制

        m_pcRateCtrl->initRCPic( frameLevel );
        4、在TEncSlice::compressSlice()中,设置CTU(LCU)级别的码率控制参数

    		if ( m_pcCfg->getUseRateCtrl() )
    		{
    			Int estQP        = pcSlice->getSliceQp();
    			Double estLambda = -1.0;
    			Double bpp       = -1.0;
    
    			if ( ( rpcPic->getSlice( 0 )->getSliceType() == I_SLICE && m_pcCfg->getForceIntraQP() ) || !m_pcCfg->getLCULevelRC() )
    			{
    				estQP = pcSlice->getSliceQp();
    			}
    			else
    			{
    				bpp = m_pcRateCtrl->getRCPic()->getLCUTargetBpp(pcSlice->getSliceType());
    				if ( rpcPic->getSlice( 0 )->getSliceType() == I_SLICE)
    				{
    					estLambda = m_pcRateCtrl->getRCPic()->getLCUEstLambdaAndQP(bpp, pcSlice->getSliceQp(), &estQP);
    				}
    				else
    				{
    					estLambda = m_pcRateCtrl->getRCPic()->getLCUEstLambda( bpp );
    					estQP     = m_pcRateCtrl->getRCPic()->getLCUEstQP    ( estLambda, pcSlice->getSliceQp() );
    				}
    
    				estQP     = Clip3( -pcSlice->getSPS()->getQpBDOffsetY(), MAX_QP, estQP );
    
    				m_pcRdCost->setLambda(estLambda);
    #if RDOQ_CHROMA_LAMBDA
    				// set lambda for RDOQ
    				Double weight=m_pcRdCost->getChromaWeight();
    				const Double lambdaArray[3] = { estLambda, (estLambda / weight), (estLambda / weight) };
    				m_pcTrQuant->setLambdas( lambdaArray );
    #else
    				m_pcTrQuant->setLambda( estLambda );
    #endif
    			}
    
    			m_pcRateCtrl->setRCQP( estQP );
    #if ADAPTIVE_QP_SELECTION
    			pcCU->getSlice()->setSliceQpBase( estQP );
    #endif
    		}
        5、在TEncSlice::compressSlice中,编码完成一个CTU之后,需要更新剩余比特数等相关的参数

    		if ( m_pcCfg->getUseRateCtrl() )
    		{
    
    			Int actualQP        = g_RCInvalidQPValue;
    			Double actualLambda = m_pcRdCost->getLambda();
    			Int actualBits      = pcCU->getTotalBits();
    			Int numberOfEffectivePixels    = 0;
    			for ( Int idx = 0; idx < rpcPic->getNumPartInCU(); idx++ )
    			{
    				if ( pcCU->getPredictionMode( idx ) != MODE_NONE && ( !pcCU->isSkipped( idx ) ) )
    				{
    					numberOfEffectivePixels = numberOfEffectivePixels + 16;
    					break;
    				}
    			}
    
    			if ( numberOfEffectivePixels == 0 )
    			{
    				actualQP = g_RCInvalidQPValue;
    			}
    			else
    			{
    				actualQP = pcCU->getQP( 0 );
    			}
    			m_pcRdCost->setLambda(oldLambda);
    
    			m_pcRateCtrl->getRCPic()->updateAfterLCU( m_pcRateCtrl->getRCPic()->getLCUCoded(), actualBits, actualQP, actualLambda,
    				pcCU->getSlice()->getSliceType() == I_SLICE ? 0 : m_pcCfg->getLCULevelRC() );
    		}
        6、在TEncGOP::compressGOP中,每编码完成一个图像,就更新剩余比特数等码率控制相关的参数

            if ( m_pcCfg->getUseRateCtrl() )
            {
                Double avgQP     = m_pcRateCtrl->getRCPic()->calAverageQP();
                Double avgLambda = m_pcRateCtrl->getRCPic()->calAverageLambda();
                if ( avgLambda < 0.0 )
                {
                    avgLambda = lambda;
                }
                m_pcRateCtrl->getRCPic()->updateAfterPicture( actualHeadBits, actualTotalBits, avgQP, avgLambda, pcSlice->getSliceType());
                m_pcRateCtrl->getRCPic()->addToPictureLsit( m_pcRateCtrl->getPicList() );
    
                m_pcRateCtrl->getRCSeq()->updateAfterPic( actualTotalBits );
                if ( pcSlice->getSliceType() != I_SLICE )
                {
                    m_pcRateCtrl->getRCGOP()->updateAfterPicture( actualTotalBits );
                }
                else    // for intra picture, the estimated bits are used to update the current status in the GOP
                {
                    m_pcRateCtrl->getRCGOP()->updateAfterPicture( estimatedBits );
                }
            }

    码率控制的相关结构

    CTU(LCU)级别的码率控制结构

    /*
    ** LCU(CTU)级别的码率控制信息
    */
    struct TRCLCU
    {
    	// 实际比特数
    	Int m_actualBits;
    	// 相应的QP
    	Int m_QP;     // QP of skip mode is set to g_RCInvalidQPValue
    	// 目标比特数
    	Int m_targetBits;
    	// lambda参数
    	Double m_lambda;
    	// 比特权重
    	Double m_bitWeight;
    	// 像素的数量
    	Int m_numberOfPixel;
    	// 帧内的代价
    	Double m_costIntra;
    	// 剩余的比特数(目标的剩余比特数)
    	Int m_targetBitsLeft;
    };
    码率参数结构

    /*
    ** 码率控制参数!
    */
    struct TRCParameter
    {
    	Double m_alpha; // alpha参数
    	Double m_beta; // beta参数
    };
    编码序列级别的码率控制结构
    /*
    ** seq序列级别(级别比gop高)的码率控制
    */
    class TEncRCSeq
    {
    public:
    	TEncRCSeq();
    	~TEncRCSeq();
    
    public:
    	Void create( Int totalFrames, Int targetBitrate, Int frameRate, Int GOPSize, Int picWidth, Int picHeight, Int LCUWidth, Int LCUHeight, Int numberOfLevel, Bool useLCUSeparateModel, Int adaptiveBit );
    	Void destroy();
    
    	// 初始化比特率
    	Void initBitsRatio( Int bitsRatio[] );
    	// 初始化gop到level的映射
    	Void initGOPID2Level( Int GOPID2Level[] );
    	// 初始化pic的码率控制参数
    	Void initPicPara( TRCParameter* picPara  = NULL );    // NULL to initial with default value
    	// 初始化LCU的码率控制参数
    	Void initLCUPara( TRCParameter** LCUPara = NULL );    // NULL to initial with default value
    	// 在处理完一帧之后更新
    	Void updateAfterPic ( Int bits );
    	// 设置总得比特率
    	Void setAllBitRatio( Double basicLambda, Double* equaCoeffA, Double* equaCoeffB );
    
    public:
    	Int  getTotalFrames()                 { return m_totalFrames; }
    	Int  getTargetRate()                  { return m_targetRate; }
    	Int  getFrameRate()                   { return m_frameRate; }
    	Int  getGOPSize()                     { return m_GOPSize; }
    	Int  getPicWidth()                    { return m_picWidth; }
    	Int  getPicHeight()                   { return m_picHeight; } 
    	Int  getLCUWidth()                    { return m_LCUWidth; }
    	Int  getLCUHeight()                   { return m_LCUHeight; }
    	Int  getNumberOfLevel()               { return m_numberOfLevel; }
    	Int  getAverageBits()                 { return m_averageBits; }
    	Int  getLeftAverageBits()             { assert( m_framesLeft > 0 ); return (Int)(m_bitsLeft / m_framesLeft); }
    	Bool getUseLCUSeparateModel()         { return m_useLCUSeparateModel; }
    
    	Int  getNumPixel()                    { return m_numberOfPixel; }
    	Int64  getTargetBits()                { return m_targetBits; }
    	Int  getNumberOfLCU()                 { return m_numberOfLCU; }
    	Int* getBitRatio()                    { return m_bitsRatio; }
    	Int  getBitRatio( Int idx )           { assert( idx<m_GOPSize); return m_bitsRatio[idx]; }
    	Int* getGOPID2Level()                 { return m_GOPID2Level; }
    	Int  getGOPID2Level( Int ID )         { assert( ID < m_GOPSize ); return m_GOPID2Level[ID]; }
    	TRCParameter*  getPicPara()                                   { return m_picPara; }
    	TRCParameter   getPicPara( Int level )                        { assert( level < m_numberOfLevel ); return m_picPara[level]; }
    	Void           setPicPara( Int level, TRCParameter para )     { assert( level < m_numberOfLevel ); m_picPara[level] = para; }
    	TRCParameter** getLCUPara()                                   { return m_LCUPara; }
    	TRCParameter*  getLCUPara( Int level )                        { assert( level < m_numberOfLevel ); return m_LCUPara[level]; }
    	TRCParameter   getLCUPara( Int level, Int LCUIdx )            { assert( LCUIdx  < m_numberOfLCU ); return getLCUPara(level)[LCUIdx]; }
    	Void           setLCUPara( Int level, Int LCUIdx, TRCParameter para ) { assert( level < m_numberOfLevel ); assert( LCUIdx  < m_numberOfLCU ); m_LCUPara[level][LCUIdx] = para; }
    
    	Int  getFramesLeft()                  { return m_framesLeft; }
    	Int64  getBitsLeft()                  { return m_bitsLeft; }
    
    	Double getSeqBpp()                    { return m_seqTargetBpp; }
    	Double getAlphaUpdate()               { return m_alphaUpdate; }
    	Double getBetaUpdate()                { return m_betaUpdate; }
    
    	Int    getAdaptiveBits()              { return m_adaptiveBit;  }
    	Double getLastLambda()                { return m_lastLambda;   }
    	Void   setLastLambda( Double lamdba ) { m_lastLambda = lamdba; }
    
    private:
    	// 总的帧数
    	Int m_totalFrames;
    	// 目标码率
    	Int m_targetRate;
    	// 帧率
    	Int m_frameRate; 
    	// gop的大小
    	Int m_GOPSize;
    	// 帧宽和高
    	Int m_picWidth;
    	Int m_picHeight;
    	// LCU的宽和高
    	Int m_LCUWidth;
    	Int m_LCUHeight;
    	// level的数量
    	Int m_numberOfLevel;
    	// 平均的比特数
    	Int m_averageBits;
    
    	// 像素的数量
    	Int m_numberOfPixel;
    	// 目标比特数
    	Int64 m_targetBits;
    	// LCU的数量
    	Int m_numberOfLCU;
    	// 比特率
    	Int* m_bitsRatio;
    	// gop的id到level的映射
    	Int* m_GOPID2Level;
    	// pic的码率控制参数
    	TRCParameter*  m_picPara;
    	// LCU的码率控制参数
    	TRCParameter** m_LCUPara;
    
    	// 剩余的帧数
    	Int m_framesLeft;
    	// 剩余的比特数
    	Int64 m_bitsLeft;
    	Double m_seqTargetBpp;
    	// alpha参数的更新
    	Double m_alphaUpdate;
    	// beta参数的更新
    	Double m_betaUpdate;
    	// 是否使用LCU分开的模型
    	Bool m_useLCUSeparateModel;
    
    	// 自适应的比特
    	Int m_adaptiveBit;
    	// 最后的lambda参数
    	Double m_lastLambda;
    };
    
    图像组(gop)级别的码率控制

    /*
    ** GOP级别的码率控制
    */
    class TEncRCGOP
    {
    public:
    	TEncRCGOP();
    	~TEncRCGOP();
    
    public:
    	Void create( TEncRCSeq* encRCSeq, Int numPic );
    	Void destroy();
    
    	// 在处理完一帧之后更新
    	Void updateAfterPicture( Int bitsCost );
    
    private:
    	// 预估一个gop占用的比特数
    	Int  xEstGOPTargetBits( TEncRCSeq* encRCSeq, Int GOPSize );
    	Void   xCalEquaCoeff( TEncRCSeq* encRCSeq, Double* lambdaRatio, Double* equaCoeffA, Double* equaCoeffB, Int GOPSize );
    	Double xSolveEqua( Double targetBpp, Double* equaCoeffA, Double* equaCoeffB, Int GOPSize );
    
    public:
    	TEncRCSeq* getEncRCSeq()        { return m_encRCSeq; }
    	Int  getNumPic()                { return m_numPic;}
    	Int  getTargetBits()            { return m_targetBits; }
    	Int  getPicLeft()               { return m_picLeft; }
    	Int  getBitsLeft()              { return m_bitsLeft; }
    	Int  getTargetBitInGOP( Int i ) { return m_picTargetBitInGOP[i]; }
    
    private:
        // 所属的码率控制序列
    	TEncRCSeq* m_encRCSeq;
    	// 该gop中,每一帧的目标比特数
    	Int* m_picTargetBitInGOP;
    	// 帧数量
    	Int m_numPic;
    	// gop总的目标比特数
    	Int m_targetBits;
    	// 还剩多少帧处理完成
    	Int m_picLeft;
    	// 还剩多少比特
    	Int m_bitsLeft;
    };
    
    图像级别的码率控制对象
    /*
    ** 图像级别的码率控制
    */
    class TEncRCPic
    {
    public:
    	TEncRCPic();
    	~TEncRCPic();
    
    public:
    	Void create( TEncRCSeq* encRCSeq, TEncRCGOP* encRCGOP, Int frameLevel, list<TEncRCPic*>& listPreviousPictures );
    	Void destroy();
    
    	Int    estimatePicQP    ( Double lambda, list<TEncRCPic*>& listPreviousPictures );
    	Int    getRefineBitsForIntra(Int orgBits);
    	Double calculateLambdaIntra(double alpha, double beta, double MADPerPixel, double bitsPerPixel);
    	Double estimatePicLambda( list<TEncRCPic*>& listPreviousPictures, SliceType eSliceType);
    
    	Void   updateAlphaBetaIntra(double *alpha, double *beta);
    
    	Double getLCUTargetBpp(SliceType eSliceType);
    	Double getLCUEstLambdaAndQP(Double bpp, Int clipPicQP, Int *estQP);
    	Double getLCUEstLambda( Double bpp );
    	Int    getLCUEstQP( Double lambda, Int clipPicQP );
    
    	Void updateAfterLCU( Int LCUIdx, Int bits, Int QP, Double lambda, Bool updateLCUParameter = true );
    	Void updateAfterPicture( Int actualHeaderBits, Int actualTotalBits, Double averageQP, Double averageLambda, SliceType eSliceType);
    
    	Void addToPictureLsit( list<TEncRCPic*>& listPreviousPictures );
    	Double calAverageQP();
    	Double calAverageLambda();
    
    private:
    	Int xEstPicTargetBits( TEncRCSeq* encRCSeq, TEncRCGOP* encRCGOP );
    	Int xEstPicHeaderBits( list<TEncRCPic*>& listPreviousPictures, Int frameLevel );
    
    public:
    	TEncRCSeq*      getRCSequence()                         { return m_encRCSeq; }
    	TEncRCGOP*      getRCGOP()                              { return m_encRCGOP; }
    
    	Int  getFrameLevel()                                    { return m_frameLevel; }
    	Int  getNumberOfPixel()                                 { return m_numberOfPixel; }
    	Int  getNumberOfLCU()                                   { return m_numberOfLCU; }
    	Int  getTargetBits()                                    { return m_targetBits; }
    	Int  getEstHeaderBits()                                 { return m_estHeaderBits; }
    	Int  getLCULeft()                                       { return m_LCULeft; }
    	Int  getBitsLeft()                                      { return m_bitsLeft; }
    	Int  getPixelsLeft()                                    { return m_pixelsLeft; }
    	Int  getBitsCoded()                                     { return m_targetBits - m_estHeaderBits - m_bitsLeft; }
    	Int  getLCUCoded()                                      { return m_numberOfLCU - m_LCULeft; }
    	TRCLCU* getLCU()                                        { return m_LCUs; }
    	TRCLCU& getLCU( Int LCUIdx )                            { return m_LCUs[LCUIdx]; }
    	Int  getPicActualHeaderBits()                           { return m_picActualHeaderBits; }
    	Void setTargetBits( Int bits )                          { m_targetBits = bits; m_bitsLeft = bits;}
    	Void setTotalIntraCost(Double cost)                     { m_totalCostIntra = cost; }
    	Void getLCUInitTargetBits();
    
    	Int  getPicActualBits()                                 { return m_picActualBits; }
    	Int  getPicActualQP()                                   { return m_picQP; }
    	Double getPicActualLambda()                             { return m_picLambda; }
    	Int  getPicEstQP()                                      { return m_estPicQP; }
    	Void setPicEstQP( Int QP )                              { m_estPicQP = QP; }
    	Double getPicEstLambda()                                { return m_estPicLambda; }
    	Void setPicEstLambda( Double lambda )                   { m_picLambda = lambda; }
    
    private:
    	// 所属的码率控制序列
    	TEncRCSeq* m_encRCSeq;
    	// 所属的码率控制gop
    	TEncRCGOP* m_encRCGOP;
    
    	// 帧的level
    	Int m_frameLevel;
    	// 像素的数量
    	Int m_numberOfPixel;
    	// LCU的数量
    	Int m_numberOfLCU;
    	// 目标比特数
    	Int m_targetBits;
    	// 帧头部/slice头部等占用的比特数
    	Int m_estHeaderBits;
    	// 预估的帧的qp
    	Int m_estPicQP;
    	// 预估的lambda
    	Double m_estPicLambda;
    
    	// 剩下的LCU的数量
    	Int m_LCULeft;
    	// 剩下的比特数量
    	Int m_bitsLeft;
    	// 剩下的像素数量
    	Int m_pixelsLeft;
    
    	// 该帧对应的LCU码率控制对象
    	TRCLCU* m_LCUs;
    	// 真实的头部占用的比特数
    	Int m_picActualHeaderBits;    // only SH and potential APS
    	// 帧内模式消耗的比特数
    	Double m_totalCostIntra;
    	// 帧内模式还剩余的比特数
    	Double m_remainingCostIntra;
    	// 帧真实占用的比特数
    	Int m_picActualBits;          // the whole picture, including header
    	// 帧的qp
    	Int m_picQP;                  // in integer form
    	// 帧的lambda参数
    	Double m_picLambda;
    };
    
    码率控制对象

    /*
    ** 码率控制管理器
    ** 管理了TEncRCSeq TEncRCGOP TEncRCPic等对象
    */
    class TEncRateCtrl
    {
    public:
    	TEncRateCtrl();
    	~TEncRateCtrl();
    
    public:
    	Void init( Int totalFrames, Int targetBitrate, Int frameRate, Int GOPSize, Int picWidth, Int picHeight, Int LCUWidth, Int LCUHeight, Int keepHierBits, Bool useLCUSeparateModel, GOPEntry GOPList[MAX_GOP] );
    	Void destroy();
    	Void initRCPic( Int frameLevel );
    	Void initRCGOP( Int numberOfPictures );
    	Void destroyRCGOP();
    
    public:
    	Void       setRCQP ( Int QP ) { m_RCQP = QP;   }
    	Int        getRCQP ()         { return m_RCQP; }
    	TEncRCSeq* getRCSeq()          { assert ( m_encRCSeq != NULL ); return m_encRCSeq; }
    	TEncRCGOP* getRCGOP()          { assert ( m_encRCGOP != NULL ); return m_encRCGOP; }
    	TEncRCPic* getRCPic()          { assert ( m_encRCPic != NULL ); return m_encRCPic; }
    	list<TEncRCPic*>& getPicList() { return m_listRCPictures; }
    
    private:
        // 当前的码率控制序列
    	TEncRCSeq* m_encRCSeq;
    	// 当前码率控制gop
    	TEncRCGOP* m_encRCGOP;
    	// 当前对应的码率控制pic
    	TEncRCPic* m_encRCPic;
    	// TEncRCPic列表(应该是一个gop中/或者一个序列中的所有帧)
    	list<TEncRCPic*> m_listRCPictures;
    	// qp参数
    	Int        m_RCQP;
    };

    码率控制是怎么样控制比特率的

    首先我们找到码率控制初始化函数TEncRateCtrl::init



    TEncRateCtrl::initRCGOP用于图像组级别的码率控制的初始化,实际初始化在TEncRCGOP::create中,其中调用了一个比较重要的函数是xEstGOPTargetBits,用于估计GOP占用的比特数

    TEncRateCtrl::initRCPic,图像级别的码率控制的初始化,实际调用TEncRCGOP::create

    这几个初始化函数的大致功能都是比特率分配,即每一帧多少比特、每一个CTU多少个比特之类的


    这些都没有什么看头,最重要的是看码率控制在HEVC中怎么样和编码器结合起来的

    重点1——计算QP:
    在TEncSlice::compressSlice中
    (1)获取bpp(bits per pixel),通过getLCUTargetBpp得到
    (2)获取Lambda参数,通过bpp等参数调用getLCUEstLambda得到
    (3)获取码率控制对象计算出的QP,通过Lambda和slice的QP等参数调用getLCUEstQP得到
    (4)把计算出来的QP保存起来,调用setRCQP

    		if ( m_pcCfg->getUseRateCtrl() )
    		{
    			Int estQP        = pcSlice->getSliceQp();
    			Double estLambda = -1.0;
    			Double bpp       = -1.0;
    
    			if ( ( rpcPic->getSlice( 0 )->getSliceType() == I_SLICE && m_pcCfg->getForceIntraQP() ) || !m_pcCfg->getLCULevelRC() )
    			{
    				estQP = pcSlice->getSliceQp();
    			}
    			else
    			{
    				bpp = m_pcRateCtrl->getRCPic()->getLCUTargetBpp(pcSlice->getSliceType());
    				if ( rpcPic->getSlice( 0 )->getSliceType() == I_SLICE)
    				{
    					estLambda = m_pcRateCtrl->getRCPic()->getLCUEstLambdaAndQP(bpp, pcSlice->getSliceQp(), &estQP);
    				}
    				else
    				{
    					estLambda = m_pcRateCtrl->getRCPic()->getLCUEstLambda( bpp );
    					estQP     = m_pcRateCtrl->getRCPic()->getLCUEstQP    ( estLambda, pcSlice->getSliceQp() );
    				}
    
    				estQP     = Clip3( -pcSlice->getSPS()->getQpBDOffsetY(), MAX_QP, estQP );
    
    				m_pcRdCost->setLambda(estLambda);
    #if RDOQ_CHROMA_LAMBDA
    				// set lambda for RDOQ
    				Double weight=m_pcRdCost->getChromaWeight();
    				const Double lambdaArray[3] = { estLambda, (estLambda / weight), (estLambda / weight) };
    				m_pcTrQuant->setLambdas( lambdaArray );
    #else
    				m_pcTrQuant->setLambda( estLambda );
    #endif
    			}
    
    			m_pcRateCtrl->setRCQP( estQP );
    #if ADAPTIVE_QP_SELECTION
    			pcCU->getSlice()->setSliceQpBase( estQP );
    #endif
    		}


    重点2——把计算出来的QP应用到编码上:
    在TEncCu::xCompressCU中
    (1)把iMinQP设置为通过码率控制计算出来的QP(调用getRCQP)
    (2)把iMaxQP设置为通过码率控制计算出来的QP(调用getRCQP)
    (3)然后利用iMinQP和iMaxQP进行编码

    	// 使用码率控制
    	// 注意这里的QP使用了,码率控制对象计算出来的QP
    	// 通过QP,码率控制对象控制了编码器的比特率
    	if ( m_pcEncCfg->getUseRateCtrl() )
    	{
    		iMinQP = m_pcRateCtrl->getRCQP(); 
    		iMaxQP = m_pcRateCtrl->getRCQP();
    	}


    重点3——根据比特率动态调整:
    (1)编码一个CTU或者图像之后,可以得到它占用的比特数
    (2)调用updateAfterLCU/updateAfterPicture,更新剩余比特数、Lambda等相关参数下一次计算QP的时候就利用这些参数重新计算,就能够自适应的改变比特率

    		if ( m_pcCfg->getUseRateCtrl() )
    		{
    
    			Int actualQP        = g_RCInvalidQPValue;
    			Double actualLambda = m_pcRdCost->getLambda();
    			Int actualBits      = pcCU->getTotalBits();
    			Int numberOfEffectivePixels    = 0;
    			for ( Int idx = 0; idx < rpcPic->getNumPartInCU(); idx++ )
    			{
    				if ( pcCU->getPredictionMode( idx ) != MODE_NONE && ( !pcCU->isSkipped( idx ) ) )
    				{
    					numberOfEffectivePixels = numberOfEffectivePixels + 16;
    					break;
    				}
    			}
    
    			if ( numberOfEffectivePixels == 0 )
    			{
    				actualQP = g_RCInvalidQPValue;
    			}
    			else
    			{
    				actualQP = pcCU->getQP( 0 );
    			}
    			m_pcRdCost->setLambda(oldLambda);
    
    			m_pcRateCtrl->getRCPic()->updateAfterLCU( m_pcRateCtrl->getRCPic()->getLCUCoded(), actualBits, actualQP, actualLambda,
    				pcCU->getSlice()->getSliceType() == I_SLICE ? 0 : m_pcCfg->getLCULevelRC() );
    		}

            if ( m_pcCfg->getUseRateCtrl() )
            {
                Double avgQP     = m_pcRateCtrl->getRCPic()->calAverageQP();
                Double avgLambda = m_pcRateCtrl->getRCPic()->calAverageLambda();
                if ( avgLambda < 0.0 )
                {
                    avgLambda = lambda;
                }
                m_pcRateCtrl->getRCPic()->updateAfterPicture( actualHeadBits, actualTotalBits, avgQP, avgLambda, pcSlice->getSliceType());
                m_pcRateCtrl->getRCPic()->addToPictureLsit( m_pcRateCtrl->getPicList() );
    
                m_pcRateCtrl->getRCSeq()->updateAfterPic( actualTotalBits );
                if ( pcSlice->getSliceType() != I_SLICE )
                {
                    m_pcRateCtrl->getRCGOP()->updateAfterPicture( actualTotalBits );
                }
                else    // for intra picture, the estimated bits are used to update the current status in the GOP
                {
                    m_pcRateCtrl->getRCGOP()->updateAfterPicture( estimatedBits );
                }
            }


    展开全文
  • HM编码代码阅读(4)——一些概念

    千次阅读 2016-04-12 17:43:24
    WPP 波前编码 SEI 图像增强提高信息 NAL单元的前两个字节是头部(第一个字节总是0,接着是NAL类型,然后是layer标志,最后是temporal标志) DPB 是解码图像缓存 VCL NAL包含编码数据 no-VCL NAL包含控制信息 IRAP...
  • 哈夫曼树和哈夫曼编码(附完整C语言代码)

    千次阅读 多人点赞 2020-12-02 23:42:06
    哈夫曼树,也叫最优二叉树。在含有给定的n个带权叶子结点的二叉树中,WPL最小的树。其中,结点的权指的是某种特定含义的数值;带权路径长度值根到结点的路径长度乘以结点权值;树的带权路径长度(WPL)是指树中所有...
  • ASCII编码

    千次阅读 多人点赞 2021-03-31 21:28:10
    ASCII(American Standard Code for Information Interchange)编码表,美国标准信息交换代码。 在计算机中,所有的数据在存储和运算时都要使用二进制数表示。 a、b、c、d这样的52个字母(包括大写)、以及0、1等数字...
  • 变分自编码器VAE:原来是这么一回事 | 附开源代码

    万次阅读 多人点赞 2018-03-23 00:00:00
    作者丨苏剑林单位丨广州火焰信息科技有限公司研究方向丨NLP,神经网络个人主页丨kexue.fm过去虽然没有细看,但印象里一直觉得变分自编码器(Variational Auto-Encoder,VAE)是个好东西。趁着最近看概率图模型的...
  • 中国于1981年发布了《信息处理交换用汉字编码字符集 基本集》GB2312-80 GB2312将代码表分为94个区,对应第一字节;每个区94个位,对应第二字节,两 个字节的值分别为区号值和位号值加32(2OH),因此称为区位...
  • ASCII(美国信息交换标准编码)表

    千次阅读 2015-03-27 14:28:30
    ASCII(美国信息交换标准编码)表 字符 ASCII代码 字符 ASCII代码 字符 ASCII代码 二进制 十进制 十六进制 二进制 十进制 十六进制 二进制 ...
  • 信息论与编码题库

    万次阅读 多人点赞 2016-11-27 22:05:09
    1. 同时掷两个正常的骰子,各面呈现的概率都是1/6,则“两个1同时出现”事件的自信息量是( )。 A、4.17bit B、5.17bit C、4.71bit D、5.71bit 解答:B。 2. 设信源概率空间为 ,则此信源的熵为( )三进制信
  • 哈夫曼编码

    千次阅读 2014-06-04 23:22:34
    Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就作Huffman编码(有时称为霍夫曼编码)。 1.2应用 哈夫曼树─即最优二叉树,带权...
  • 字符编码那些事--彻底理解掌握编码知识

    千次阅读 多人点赞 2020-05-04 16:42:33
    每一个程序员都不可避免的遇到字符编码的问题,很多人在字符编码方面同样遇到不少问题,而且一直对各种编码懵懵懂懂、不清不楚。这篇文章就是针对字符编码中的一些问题进行了详细的阐述,能从根本上理解字符编码
  • 前言 你是否有过这样的疑惑? 1.我的代码里面中文注释在自己电脑上是可以正常显示的,但是换了别的电脑出现了乱码。 2.想写跨平台程序,但是在Windows上明明正常的,...不知道计算机是如何显示编码的 7.分不清unic
  • 字符编码的前世今生

    千次阅读 2017-09-18 17:24:07
    前言很多程序员对字符编码不太理解,虽然他们大概知道 ASCII、UTF8、GBK、Unicode 等术语概念,但在写代码过程中还是会遇到各种奇怪的编码问题,在 Java 中最常见的是乱码,而 Python 开发中遇到最多的是编码错误,...
  • Windows操作系统中使用的代码页 Windows平台上的GUI程序使用ANSI代码页,而在控制台程序使用OEM代码页(以便向后兼容)。...这两个代码页在前128个字符的编码是一样的,但后128个字符的编码可能不一致。在
  • 什么叫代码覆盖率

    千次阅读 2007-06-14 15:09:00
    什么叫代码覆盖率什麼代碼覆蓋率?它的作用是什麼?在測試流程過程中,它什麼時候做?另外,有什麼工具可以實現該功能?它與開發代碼中的代碼覆蓋率有什麼區別沒?在測試中的代碼覆蓋率是指,你运行测试用例后,走过...
  • 信源编码与信道编码

    万次阅读 多人点赞 2017-03-26 17:02:44
    但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损编码,另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余,更加有效、经济地传输,最常见的应用形式就是压缩。...
  • MySQL字符集和校对规则MySQL的字符集是用来定义MySQL存储字符串的方式,校对规则(有的软件排序规则)则是用来定义了比较字符串的方式。字符集和校对规则是一对多的关系。每种字符集都有一个默认校对规则。查看...
  • 信源编码和信道编码

    千次阅读 2018-12-06 15:14:59
    但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损编码,另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余,更加有效、经济地传输,最常见的应用形式就是压缩。...
  • 赫夫曼编码原理与实现

    千次阅读 2016-10-11 16:10:58
    1951年,Huffman在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,Huffman放弃对已有编码的研究...
  • 最近有个需求是定位后根据定位的经纬度获取当前地址的详细信息,例如获取街道名称,街道号,乡镇街道编码,区域编码信息。 于是乎找到了高德的逆地理编码接口,看了看正好符合我的需求。然而使用起来并不顺利! ...
  • JAVA核心知识点--字符编码

    万次阅读 2017-06-18 16:47:13
    为什么要编码? 常用编码格式 ASCII码 ISO-8859-1 GB2312 GBK UTF-16 UTF-8 在I/O操作中存在的编码 在内存操作中的编码 在Java Web中涉及的编解码 URL的编解码 HTTP Header的编解码 POST表单的编解码 ...
  • 汉字编码之GBK编码(附完整码表)

    万次阅读 多人点赞 2016-03-04 12:21:24
    继续字符编码的学习。今天介绍一下GBK(汉字内码扩展规范),GB 2312 GB18030。引用网友的话可以概括一下: GBK和UTF8的区别:GBK就是在保存你的帖子的时候,一个汉字占用两个字节。。外国人看会出现乱码,此为我中华...
  • ASCII码表【美国信息交换标准代码

    万次阅读 2014-02-17 14:37:47
    国际上普遍采用ASCII编码(American Standard Code for Information Interchange,美国信息交换标准代码) 作为通用的字符编码。 ASCII编码的作用就是给英文字母、数字、标点、字符转换成计算机能识别的二进制数...
  • STM32 TIM 编码器模式采集编码器信号

    千次阅读 2019-10-26 10:22:25
    ## 什么是正交解码? 对于常用增量式编码器,光学编码器,采用带槽圆盘,一侧...增量编码器通常有A,B两相信号,相位相差90°,所以也叫正交,还有一个复位信号是机械复位,即转了一圈,复位信号会有一个跳变沿。具体如
  • python编码规范

    万次阅读 多人点赞 2019-08-14 16:30:16
    PE8基本规范: 建议修改在使用的 IDE 中修改 PEP8 的...1、国际惯例,文件编码和 Python 编码格式全部为 utf-8 ,例如:在 Python 代码的开头,要统一加上 # -- coding: utf-8 --。 2、Python 代码中,非 ascii 字...
  • 字符编码简介

    千次阅读 2016-04-11 22:17:55
    1. ASCII码ASCII (American Standard Code for Information Interchange, 美国标准信息交换代码),是基于拉丁字母的一套编码系统,主要用于显示现代英语和其他西欧语言。它是现今最通用的单字节编码系统。 单个字节...
  • python字符串编码及乱码解决方案

    万次阅读 2015-03-08 20:26:50
    字符编码详解 [字符编码ASCII,Unicode和UTF-8] 主要非英文字符集的编码范围 范围 编码 说明 2E80~33FFh 中日韩符号区 收容康熙字典部首、中日韩辅助部首、注音符号、日本假名、韩文音符, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,807
精华内容 57,122
关键字:

代码也叫信息编码