请选择 进入手机版 | 继续访问电脑版

C++编程

 找回密码
 立即注册

QQ登录

只需一步,快速开始

楼主: ID紫麒麟

紫麒麟笔记_1杂乱

[复制链接]

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-4 17:29:01 | 显示全部楼层
本帖最后由 ID紫麒麟 于 2016-5-4 17:40 编辑

今天说一个快速判断一个32位的字中是否存在值为0的byte,记得当时看到这个算法的时候挺有意思的。今天突然想起来,就随便搜索了一下。印象中小甲鱼c语言视频里面好像有,或者是什么视频里面有的。
下面这个只是一个简单的应用,其实有更多更好的用处的。

首先为什么要做这样的判断呢?

    当你要strcpy活着strcmp或者hash一个字符串的时候,传统的方法是每个byte进行比较。以strcpy为例,当一个字符串比较长,我们用32(或者64位)的字长进行copy的话,一次拷贝会拷贝4个byte,能节省很多时间(忽略内存对齐等情况)。

    但是,使用32位的字长进行拷贝一个难点就是判断字符串的结尾,因为字符串长度不一定是4的整数倍,每次从内存中取4个byte,我们需要判断这4个byte中是否有某个byte是0,从而判断字符串是否结束。

    最传统的做法就是对每个字节进行一次判断,或者将所有字节乘起来,看结果是否是0:http://www.spongeliu.com/

unsigned char * p = (unsigned char *) & v;  bool hasNoZeroByte = *p && *(p + 1) && *(p + 2) && *(p + 3);
    上面的代码需要12步操作,并且需要若干乘指令,效率不高。

    一种传统有效的方法是通过对每个byte进行一次掩码的操作来判断是否存在0:

bool hasNoZeroByte = ((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000));
    上面的操作相当于取出每一个byte,并进行与操作,最终判断是否是0,这样做需要进行7次操作。

    那么,是否有更快的方法呢? 看下面的表达式:

unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
    这种方法进行了5次操作来完成整个工作!具体是怎么做到的,让我们仔细来看:

    首先,将v同 0x7f7f7f7f 进行&操作,目的是将v中每个byte的最高位清零;

    然后,再加上 0x7f7f7f7f 的目的是让每个byte的低7位溢出,这个时候只要每个byte的低7位不全是0,那么就会溢出;

    随后,我们再将得到的数同原先的v进行一个“按位或”的操作,这样每个byte的最高位都会被置为1,除非这个byte初始为0(若初始为0,则第二步的时候不会溢出,第三步的时候0|0还是0);

    再然后,我们再讲得到的数同 0x7f7f7f7f “按位或”,则如果初始的数不包含0byte,我们就会得到0xffffffff,否则我们得不到这个数;

    最后,进行一个“按位否”操作,就会得到一个0或者非0。

    我们用两个例子来更直观的说明,先举一个不包含0byte的32位数,以 0x5FF23D6E 为例:

0x5FF23D6E & 0x7F7F7F7F = 0x5f723d6e;  //每个byte的高位全清00x5f723d6e + 0x7F7F7F7F = 0xdef1bced; //对每个byte的低7位进行溢出,只有当一个byte是0或者是“10000000”的时候不会溢出0xdef1bced | 0x5FF23D6E = 0xdff3bdef; //或上原来的数,这是除非一个byte初始是0,否则最高位都会是10xdff3bdef | 0x7F7F7F7F = 0xffffffff; //将所有bit置为1~ 0xffffffff = 0; //得到结果
    再使用一个包含0byte的32位数为例,以 0x5FF2006E 为例:

0x5FF2006E & 0x7F7F7F7F = 0x5f72006e;  //每个byte的高位全清00x5f72006e + 0x7F7F7F7F = 0xdef17fed; //对每个byte的低7位进行溢出,这个时候因为第三个byte是0,所以这个byte的最高位不是10xdef17fed | 0x5FF2006E = 0xdff37fef; //或上原来的数,第三个byte最高位不是10xdff37fef | 0x7F7F7F7F = 0xffff7fff; //第三个byte最高位不是1,其他所有位都是1~ 0xffff7fff = 0x8000; //得到结果
    这种方法在一些字符串操作的性能优化,尤其是当大量字符串需要被哈希、拷贝时还是比较有效的。
http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-5 10:19:13 | 显示全部楼层
代码结构分层很重要啊,特别是针对于c语言这种比较自由的语言,没有c++中class里面的public、private、protected帮助程序员建立层次的方式。所以static、extend关键字在纯c语言中利用的比较多。好了,说了一点儿虚的东西,今天再谈一个知识点儿吧:
自行百度一下:include与extend的区别。
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-5 10:39:09 | 显示全部楼层
今天再记录下一点儿东西吧:
在C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
至于这5个区的知识点,很多很多。
还记得原来有个人给我讲这5个区的概念的时候,帮我梳理这部分的东西。
不晓得他过的如何了,其实这个概念里面还是有很多很多东西需要去理解的。
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-5 11:46:54 | 显示全部楼层
以下文字摘自《Windows 并发编程指南》,版权归原作者所有,仅供学习和研究参考。
对于任何良好的临界域实现方式来说,都存在一系列的需求。
1.  保持互斥性,无论在什么情况下,只能有一个线程可以进入临界域。
2.  保证进入临界域和退出临界域等操作的活跃性(Liveness)。系统可以不断地向前推进,这意味着这个算法既不能产生死锁,也不能产生活锁。具体来说,如果给定无限长的时间,那么每个到达临界域的线程都将进入临界域,没有任何线程会无限期地停留在临界域中。
3.  提供某种程度的公平性,例如根据线程到达临界域的时间来确定它相对于其他线程的优先级。虽然这并不意味着必须存在某种确定的公平性保证(例如先进先出),但临界域经常会努力实现某种程度的公平性。
4.  另一个主观意义上的标准就是低开销。在进入临界域和离开临界域时保持较低的开销是非常重要的。在底层的系统软件中经常会大量地使用临界域,例如操作系统,因此在临界域的实现效率上存在着很大的压力。
可以采用多种方法来实现临界域。不过,目前所有的互斥机制都依赖于一组原子的比较和交换(Compare  and Swap, CAS)硬件指令以及操作系统的支持。但在介绍这些指令之前,我们首先看看为什么需要硬件来提供支持。换句话说,通过我们熟悉的串行编程结构来实现EnterCriticalRegion和LeaveCriticalRegion难道不是很容易吗?

这种最简单,最初级的方法根本就不可行。我们可以设计一个标志变量,初始值为0,当有线程进入到临界域时将这个变量设置为1,而在离开临界域时设置为0,。每个试图进入临界域的线程都将首先检查这个标志,如果这个标志为0,这进入临界域并且将标志设置为1.

[cpp] view plain copy
int   taken = 0;  
  
void EnterCriticalRegion()  
{  
    while(taken != 0)   // 忙等待  
    taken = 1;             //表示临界域已经被获取了  
}  
  
void  LeaveCriticalRegion()  
{  
       taken = 0;    //表示临界域已经被释放了  
}  
这种实现方式非常糟糕。原因在于,在算法中使用的一系列读操作和写操作都不是原子的。假设有两个线程在读取taken时都获得了0,并且根据这个信息都决定将1写入taken。这两个线程都会认为自己获得了这个临界域,但它们却在同时运行临界域中的代码。这正是我们最初使用临界域所要避免发生的事情。
在分析现有的技术之前,即在现代临界域中使用的技术,我们将首先回顾过去40多年中在互斥的实现方式上经历的曲折发展道路

严格交替

我们首先可能会尝试通过严格交替(Strict  Alteration) 来实现互斥行为,首先将所有权交给线程0,然后线程0在执行完时再把所有权交个线程1,而线程1在执行完成时又接着把所有权交给线程2,以此类推,直到N个线程,最后由线程N-1将所有权交回给线程0,此时就完成了对临界域中代码的执行。这种方式的实现形式可能像下面的代码这样:

[cpp] view plain copy
const  int  N= ....;        //系统中线程的编号  
int  turn  = 0;        //线程0首先执行  
  
void   EnterCriticalRegion(int i)  
{  
     while(turn != i)    // 忙等待  
     // 其他某个线程将所有权交给了我们,现在我们拥有临界域  
}  
  
void  LeaveCriticalRegion(int i)  
{  
    //将所有权交回给下一个线程(可能交回到线程0)  
   turn = (i+1) % N;  
}  
这个算法能够实现N个并发线程在使用临界域时的互斥性。在这种模式中,每个线程都有一个唯一的标识,取值范围为【0....N】,这个标识将被作为参数i的值传递给EnterCriticalRegion。变量turn表示当前哪个线程被允许在临界域中执行,并且当线程试图进入临界域时,它必须等待另一个线程将所有权交给它,在上面的示例中使用的是忙等待。在这个算法中,我们必须指定哪个线程最先执行,在示例中选择线程0首先执行并且在外部将turn初始化为0.在离开临界域时,每个线程都要通知下一个线程开始执行:设置相应的turn,如果达到了线程的最大数量,则将turn回卷为0,否则将turn递增1。

在严格交替中存在一个问题:在决定将临界域的所有权交给某个线程时,并没有考虑线程到达临界域的时间。相反的是,在算法中存在一种预定义的顺序:首先是0,然后是1,---,N-1,然后又回到0,等等。这种顺序是固定的,不可修改。这种顺序不可能是公平的,它经常导致一个不在临界域中的线程阻碍另一个线程进入临界域。这可能会降低系统的活跃性,但却会降低程序的性能和可伸缩性。只有当线程有规律地进入临界域和退出临界域时,这个算法才能发挥作用。另一个问题是,在临界域中不能容纳可变数量的线程。我们很难知道有多少个线程将进入某个临界域,并且更难知道线程的数量在进程的生命周期中是否保持不变。

Dekker和Dijkstra提出的算法(1965)

在第一个被广泛接受的互斥问题解决方案中并没有使用严格交替,它是由一位读者在回应E.W.Dijkstra于1965年发表的一篇文章时提出的,Dijkstra在这篇文章中提出了互斥问题,并且寻求对这个问题的解决方案。一个叫做T.Dekker的读者提交了一个解决方案能够满足Dijkstra的标准,但只能适用于两个并发的线程。这种算法称为“Dekker算法”,Dijkstra随后在同年发布的另一篇文章中扩展了这种算法使其可以适用于N个线程。

Dekker提出的解决方案与严格交替是类似的,都需要分配次序,但在这个解决方案中,每个线程可以表示是否希望进入临界域。当一个线程想要进入临界域但却还没有轮到它的次序时,它可以“窃取”其他不打算进入临界域(即不在临界域中)的线程的次序。

在下面的示例中定义了一个共享的布尔数组flags,这个数组包含两个元素并且都被初始化为false。当线程希望进入临界域时,它将true保存到相应位置的元素中(线程0使用下标为0的元素,线程1使用下标为1的元素),并且在退出时将false写入这个元素。当且仅当线程希望进入临界域时才执行这些操作。这种方式是可行的,因为线程首先写入到一个共享的数组flags,然后判断另一个线程是否也已经写入到数组flags。我们可以确保,如果将true写入flags,然后从另一个线程对应的元素中读取false,那么另一个线程将看到这个true值。(注意,在现代处理器中是以乱序方式来执行读操作和写操作,这种执行方式将破坏这种假设。)

在算法中必须处理这两个线程同时进入临界域的情况。算法通过共享变量turn来做出决策,正如在前面已经看到的情形。就像在严格交替中,当两个线程都希望进入临界域时,只有当其中一个线程看到turn等于它自己的索引时,才会进入到临界域,而其他的线程将不再希望进入(也就是,它在flags中元素的值为false)。如果某个线程发现两个线程都希望进入但却还没有轮到它的次序,那么这个线程将“后退”并且将它的flags元素设置为false,然后等待turn 发生变化。这就使另一个线程进入临界域。当线程离开临界域时,它只是将对应的flags元素重置为false,并且修改turn。

下面的代码给出了完整的算法

[cpp] view plain copy
static bool[] flags = new bool[2];  
static int turn = 0;  
  
void EnterCriticalRegion(int i)   // i只能是0或者1  
{  
       int  j = 1-i;        //另一个线程在flags中的索引  
       flags[i] = true;   // 表示希望进入临界域  
       while(flags[j])   //等待直到另一个线程不希望进入临界域  
      {  
            if(turn == j)  //还没有轮到我们,因此必须后退并且等待  
            {  
                  flags[i] = false;  
                  while(turn == j)    // 忙等待  
                  flags[i] = true;  
             }  
      }  
}  
  
void LeaveCriticalRegion(int i)  
{  
    turn = 1-i;          // 让出次序  
    flags[i] = false;  // 退出临界域  
}  
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-5 11:47:28 | 显示全部楼层

Dijkstra对这个算法进行了修改以支持N个线程。虽然这个算法仍然要求N是一个确定值,但它能够适用于线程数量小于N的系统,从而使得算法更为适用。
这个算法与Deckker的算法略微不同。首先定义一个大小为N的数组flags,但数组中的元素不是布尔类型而是一种三值(Tri-Value)类型。每个元素的值都可以是以下三个值之一: passive,表示这个线程此时不打算进入临界域;requesting,表示这个线程正在尝试进入临界域;active,表示这个线程当时正在临界域中执行。

线程在到达临界域时,它将把数组flags中的对应元素设置为requesting以表示希望进入临界域。然后,它将尝试“窃取”当前的次序:如果当前的次序被分配给一个并不打算进入临界域的线程,那么这个已达到的线程将把turn设置为它自己的索引。一旦这个线程获得了turn,那么它将把状态设置为active。然而,在线程继续执行之前,它必须验证没有其他的线程在同时也窃取了次序并且可能已经进入到了临界域,否则将破坏互斥行为。具体的验证方式就是确保没有其他线程的标志是active。如果发现了另一个活跃的线程,那么这个已到达的线程将后退并且回到requesting状态,并且直到它能进入临界域才继续执行。当线程离开临界域时,它会将相应的标志设置为passive。

下面是一个用C#编写的示例实现。

[csharp] view plain copy
const  int  N = ...;  // 可以进入临界域的线程编号  
enum  F : int  
{  
    Passive,  
    Requesting,  
    Active  
}  
  
F[]  flags = new new F[N]; // 所有元素被初始化为passive  
int  turn = 0;  
   
void   EnterCriticalRegion(int i)  
{  
     int j;  
     do  
     {  
           flags [ i] = F.Requesting;  // 表示希望进入临界域  
           while(turn != i)  // 保持自旋,直到轮到自己的次序  
                  if(flags[turn] == F.Passive)  
                  turn = i;   // 窃取次序  
                  flags[i]  = F.Active;   // 宣告正在进入临界域  
                  //确保没有其他的线程已经进入到临界域      
                  for(j = 0;  j<N &&(j == i || flags[j]  !=  F.Active); j++);  
     }  
    while (j<N);  
}   
  
void LeaveCriticalRegion(int i)  
{  
      flags[i]  = F.Passive  // 表示离开临界域  
}  
Peterson提出的算法(1981)

在Dekker算法发布了大约16年之后,G.L。Peterson提出了一种简化算法,并且在它的文章”Myths  about  Mutual  Exclusion“ 中给出了详细的描述。这种算法简称为Peterson算法。在不到两页的篇幅中,他给出了一个适用于两个线程的算法,以及一个适用于N线程的算法,这两个算法都比Dekker和Dijkstra最初提出的算法要简单。

为了简单起见,我们这里只介绍适用于两个线程的算法。共享变量都是相同的,包括一个flags数组和一个turn变量,这与Dekker算法是一样的。然而,与Dekker算法不同的是,当线程希望进入临界域时,它将首先把flags中对应的元素设置为true,然后立即把turn让给其他的线程。接下来,这个线程将等待另一个线程不在临界域中或者知道turn值重新回到这个线程。

[cpp] view plain copy
bool[]   flags = new bool[2];  
int  turn = 0;  
  
void EnterCriticalRegion(int i)  
{  
     flags[i] = true;   // 表示希望进入临界域  
     turn  = 1-i;  
     //等待直到临界域可用或者轮到了我们的次序  
     whle(flags[1-i] && turn != i)  // 忙等待  
}  
  
void  LeaveCriticalRegion(int i)  
{  
     flags[i] = false;  // 退出临界域  
}  

与Dekker算法一样,Peterson算法同样盲足所有基本的互斥性、公平性以及活跃性。但这个算法更为简单,因此在讲解互斥时比Dekker算法用得更多。
Lamport提出的Bakery算法(1974)

L.Lamport同样提出了一种算法,称为Bekery算法。这种算法能够很好地适用于不同数量线程的情况,此外这个算法的好处在于,如果某个线程在进入临界域或者退出临界域发生失败,那么并不会破坏系统的活跃性,而在之前介绍的其他算法中都存在这个问题。所要求的就是,这个线程必须将它的票号(Ticket Number)重新设置为0并且移动到非临界域。Lamport希望将它的算法应用与分布式系统中,因为在任何一个分布式系统算法中,容错(Fault  Tolerance)都是一个非常关键的属性。

这个算法称为Bakery(面包店)算法,主要是因为它的工作原理有点类似于面包店的运作方式。当一个线程到达时,它将获得一个票号,只有当这个线程的票号被叫到时(或者更准确地说,只有当那些票号更小的线程都已经执行完毕后),这个线程才被允许进入临界域。这个算法能够正确地处理边界情况:多个线程通过线程之间的某种排序方式被分配到了同一个票号-------例如,唯一的线程标识、名字或者其他可进行比较的属性-------这种情况将破坏平衡。以下是这个算法的示例实现。

[cpp] view plain copy
const int N= ....;   //可以进入临界域的编程编号  
int[]   choosing = new int[N];  
int[]   number = new int[N];  
  
void EnterCriticalRegion(int i)  
{  
     // 让其他线程知道正在选择一个票号  
     // 然后找到当前最大的票号并且加1  
     choosing[i]  = 1;  
     int m = 0;  
     for(int j = 0; j<N; j++)  
     {  
           int jn = number[j];  
           m = jn > m? jn : m;  
      }  
      number[i]  = 1+ m;  
      choosing[i] = 0;  
  
for(int j=0; j<N; j++)  
{  
    //等待线程完成选择  
    while(choosing[j] != 0)  //忙等待  
    //等待拥有更低票号的线程执行完成。如果获得了与另一个线程相同的票号,  
    // 那么ID值最小的线程将首先进入  
  
     int jn;  
     while((jn = number[j]) != 0 && (jn == number[i] && j<i)))         
     //忙等待  
}  
  //叫到我们的票号,进入临界域....  
}  
  
void LeaveCriticalRegion( int i)  
{  
    number[i]  = 0;  
}  
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-6 13:50:49 | 显示全部楼层
今天头好晕啊,随便写个东西吧。

百度一下虚析构函数。
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-6 18:23:22 | 显示全部楼层
临界区,互斥量,信号量,事件的区别
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-9 10:00:43 | 显示全部楼层
本帖最后由 ID紫麒麟 于 2016-5-9 15:51 编辑

如今操作系统好多啊
windows系列:
windowsXP、win7、win8、win10、winCE、windows Server 2003、windows Server 2008
类Unix系列:
这个就多了什么IBM、HP之类的公司应该都有自己的Unix系统
另外一个就是版本繁多的linux系统了,什么Ubuntu(四年一个永久支持版,8.04、12.04、16.04等等吧)、Linux Mint、中国的麒麟(kylin)、银河、雨林木风、深度(deep linux)
手机上的安卓。。。
苹果系统。。。
winPhone。。。
Ubuntu似乎也有手机版
Vxworks系统
好多好多系统啊,windows可能是中国PC电脑上安装的最多的了(界面形象,操作形象,图形化//臃肿驳杂,“慢”),linux Redhat似乎是中国很多小服务器比较多的(高吞吐量,//“低响应”),手机方面就是苹果和安卓多(平稳,小巧,耗电量低//“性能限制”,大小限制,手持设备限制。。随着事件的增长,性能来说,总会有一天提高的)。
嵌入式系统方面也是很多很多。。。

以上只是我一家之言,不管对错的浑沦提出,一旦有任何伤害或者什么责任,本人概不负责
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-10 16:08:34 | 显示全部楼层
本帖最后由 ID紫麒麟 于 2016-5-10 16:28 编辑

今天写一个我没看懂的东西
http://www.taidous.com/bbs/thread-40590-1-1.html#userconsent#
这个文章是昨天写的,最后说什么自己花了五天,是最困难的bug之一,看着有点儿不知所云

再说一点儿东西吧,就是很多开源的框架可以尝试去解读,最好找一些麻雀虽小五脏俱全的开源代码最好了。
比如一些常见的
tinyxml
cjson
protobuf
lua
nginx
…………
回复 支持 反对

使用道具 举报

18

主题

225

帖子

971

积分

高软

Rank: 4

积分
971
 楼主| 发表于 2016-5-13 16:16:21 | 显示全部楼层
ffmpeg里面音频和视频是混合在一起的,其中pts和dts这两个时间戳有时候很头疼。
最近头疼这个问题很久很久很久了。
看到一行代码,手头没办法记下来,就记在这里了。
frame->pts = s;
s = frame->pts + frame->nb_samples;
音频的nb_samples一般是0
视频的nb_samples一般是1
但是如果是多音轨的这个可能会不成立。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|C++编程  

GMT+8, 2019-8-19 07:16 , Processed in 0.109375 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表