聚星亭

吾笨笨且懒散兮 急须改之而奋进
posts - 74, comments - 166, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
题目要求:
         纯C 、不准使用汇编,不准使用临时变量(当然包括全局变量)实现一个strlen 函数。 
就是说,可以利用的资源只有那个参数,但是有个要求就是不许破坏原字符串。 

         我能想到的方法就是递归,所以我给出的答案是:
unsigned int mystrlen(char *pszString)
{
    
if (*pszString == '\0')
    {
        
return 0;
    }

    
return mystrlen(++pszString)+1;
}

        出题的朋友说,这样跟算是使用了内存,而且这样递归会溢出,PASS掉了……,没有办法,知道求助我的同学,他们给出了这样的答案:
int StrLlen(char * p)
{
    
*((int *)&- sizeof(int* 2 ) = 0;
    
while ( (*p))
    {
        (
*((int *)&- sizeof(int* 2 ))++ ;
        p
++;
    }
    
return *((int *)&- sizeof(int* 2 );  
         很佩服同学们的敏捷思路,不过这样算是使用临时变量呀,所以也很自然的被PASS了,经过一个小时的漫长等待,出题的朋友给出了经典的让人吐血的答案:
strlen(char *p)
{
      
if(p[0== 0return 0;
      if (p[1== 0return 1;
         .....
      if(p[10000== 0return 10000;
      ....
}

         哎……

下面是应 OnTheWay 朋友的要求,给出的解释:
         首先,题目本身的性质,我感觉就是消遣,肯定不会有人无聊到不用变量写strlen,也肯定不会应用到实际情况,所以,大家不要太认真……

         再就是从技术的角度来讲,空明流转 和 OnTheWay 说的 访问非法内存 我觉得应该不是这样的,下面就我的理解,做出的解释如下:
          
/**************************************************************************
    介于各位看官C水平不同,我在函数中做点儿解释性的说明。
当然,由于本人水平也很菜,注释仅限个人理解范畴,如有不对,请批评指正……
***************************************************************************
*/
int StrLlen(char * p)
{
    
// (int *)&p 这个应该不用解释,就是取参数的地址。
    
// sizeof(int) * 2 求出两个int的大小。
    *((int *)&- sizeof(int* 2 ) = 0;
    // 由于这里是减一个数值,由此,这句话就相当于申请两个int变量,并将第一个变量初始化为0。
    // 如果这句话变成*((int *)&p + sizeof(int) * 2 ) = 0; 那就破坏了程序的参数,算是非法访问内存,可是人家是减的不是加
    while ( (*p))
    {
        (
*((int *)&- sizeof(int* 2 ))++// 使用刚才申请的变量作为累加器,存放字符串长度。
        p++;
    }

    
return *((int *)&- sizeof(int* 2 ); // 返回字符串长度。
         以上注释,纯粹是我的个人理解,本人刚学C语言,理解可能有误,所以特地写了一个测试程序,验证一下上面的注释:


      查看程序运行情况,看看是否有问题……

      运行没有问题,再调试看看内存情况:

            我截取的汇编代码,相关的内存情况我也截取了,有汇编有真相……


          这里跟我预期想的减两个int大小有点出入,为什么减的是0x20?有待继续考证,不过不影响我们的理解,它是减的地址,相当于申请变量,减0x20相当于申请了8个变量,而不是加了0x20,因此栈内存是安全的,不存在非法操作内存的情况……

          另外,这个就是一个娱乐,如果我的解释看官明白了,我很欣慰,如果我讲述的有问题,请回复我,我修改,如果没看明白,就当我在逗自己玩……



路人甲
0x20解释:
(int*)&p 表示是一个指针,指针的在32在系统是占4个字节,sizeof(int)*2 = 8; 减8表示表示往回退8个指针,也就是8*4=32=0x20。这个就是T a[size]中,a+n 是表示(&(a[0])) + sizeof(T)*n

Feedback

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 01:20 by 一剑
哈哈哈

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 02:38 by 流年
额,无语了

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 09:09 by 丽可酷购物网站
空间看见爱是空间的即可撒

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 10:43 by chaoswork
我觉得
int StrLen(char *pszString)
{
return printf("%s",pszString);
}
不算犯规吧=。=
不想输出的话就用sprintf

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 10:55 by XGuru
@chaoswork
嘿嘿,开始还看错了,试了下没想到printf真的有返回值呢~
http://www.geekinterview.com/kb/printf-Function-Return-Value.html

不过题目“可以利用的资源只有那个参数”,printf应该不能用把

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 11:59 by 小时候可靓了
那个if的,好像不错!

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 13:13 by 空明流转
第二的答案太shit了。。。会crack掉的。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-24 18:45 by OnTheWay
最后出题人给出的算是答案吗?!
假如给定的字符串有1亿个字符,那么是否需要写1亿个if?
盼给出解释。
第二个答案根本就是访问非法内存。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-24 22:50 by besterChen
@chaoswork
我自己递归的函数都算违规,调用库函数也是一样违规的……

@空明流转
@OnTheWay
我在原文后给出追加解释,希望我理解的没有什么问题……

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-25 09:25 by OnTheWay
访问非法内存的意思是:访问了你没有权限操作的内存,或者说是你不应该操作的内存。
(int *)&p - sizeof(int) * 2 ,这句代码就是访问了不应该访问的内存 ,虽然是 - sizeof(int) * 2。
这种操作是依据于实现的,是危险的操作,当然了访问非法内存并一定会死机。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-25 20:21 by besterChen
@OnTheWay
我感觉C支持嵌汇编,而这种用法符合汇编逻辑,我感觉是没问题的不危险,而且一定不会死机的,或许是我刚开始学,理解不深入吧……
倘若这位兄台有心,可否教授一二……

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-26 13:12 by shaker(太子)
这种操作是依据于实现的,具体的平台和编译器会有不同的实现!
也许目前在你的系统上是ok的,但换一个系统就不一定了。
你所说的汇编逻辑只是在win32+x86+VC上建立的。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-26 17:28 by test
template<int T>
int smstrlen(char*p)
{
if(p[T]==0)
return T;
return smstrlen<T+1>(p);
}
template<>
int smstrlen<500>(char*p)
{
if(p[500]==0)
return 500;
return -1;
}

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-26 17:48 by 12
强烈怀疑你同学修改了main()的参数内存

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-26 22:30 by OnTheWay
template<int T>
int smstrlen(char*p)
{
if(p[T]==0)
return T;
return smstrlen<T+1>(p);
}

想到这种方法很不错!我没有想到。
不过这种方法只是把递归的逻辑改成了模板实现,并且需要
template<>
int smstrlen<500>(char*p)
{
if(p[500]==0)
return 500;
return -1;
}
这个特化的模板来结束编译器的递归推导过程。

此种解法的思想很好,不过此种方法存在的限制比递归还严重(需要特化,而这种特化太大了不好,太小了又可能出现问题)。


一下是使用尾递归的一种实现:
int MyStelen(char *str, int size = 0)
{
return (*str++ == '\0') ? size : MyStelen(str, size + 1);
}

这种尾递归,不存在stack over flow的问题。不过没有多大实际意义,仅仅具有学术讨论价值,还是使用循环的方式比较好。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-27 15:45 by 路人甲
0x20解释:
(int*)&p 表示是一个指针,指针的在32在系统是占4个字节,sizeof(int)*2 = 8; 减8表示表示往回退8个指针,也就是8*4=32=0x20。这个就是T a[size]中,a+n 是表示(&(a[0])) + sizeof(T)*n

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-27 22:01 by besterChen
@shaker(太子)
是啊,以前学习的太杂,现在不想一直浮在水面上,想专一写,所以,只学习了您说的这个平台,对于别的环境不了解,嘿嘿

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-27 22:03 by besterChen
@路人甲
谢谢你的教诲,受教了,嘿嘿

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-28 09:49 by 溪流
申请栈内存的操作时 sub esp, xx
文中拿到的内存虽然也是在那个位置,但是 esp 未变化,这并不能算合法申请内存,而是在用不属于自己的内存

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享[未登录]  回复  更多评论   

2010-04-28 19:48 by besterChen
@溪流
恩,有道理,我没有考虑过这个,是我的疏忽,嘿嘿……

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-29 15:45 by lymons
如果大家对内存中的栈空间(stack)有足够的了解的话,这道题就变的容易的多了。

首先bz给的答案是对的。
原理就是利用栈空间中的一个空闲位置来存储我们的计算数据。
实际上就是把这个空闲位置当成一个临时的存储空间来用。
比如,你可以写的更简单一些。
int mystrlen(char *string)
{
*(long *)(&string - sizeof(char *) - 4) = (long)string;
while(*string++);

return ((long)string - *(long *)(&string - sizeof(char *) - 4) - 1);
}
写法虽然不同,但原理都是完全一样的。

>>>>这里跟我预期想的减两个int大小有点出入,为什么减的是0x20?
这有两个原因:
1。 栈空间永远是从高地址向低地址的方向发展的
2。 编译器至少给当前函数分配20h(32)个字节的栈空间,即使该函数里没有一个局部变量

所以,ESP(栈顶指针)会向下减去20h个字节。这样,这32个字节是给当前函数使用的,在bz的例子中,因为函数里没有一个局部变量,所以,这32个字节都是可以任意读写访问的。

只要您找到这个空闲空间的地址,你当然就可以往里面写入自己的数据喽。

只要明白上面的事情,代码就容易编写了。
&string 就是 形参string在栈空间中的地址,把这个地址减去一个sizeof(char *),这是因为,形参string下面放的是函数的返回地址(不是返回值哦),它是不能被修改的,否则就会被hack了。然后再减去4个字节,这个就是该函数的第一个空闲位置的地址了。

其实,了解栈的朋友都知道,当前正在被执行的函数永远是处于栈顶的位置,所以栈顶下面的空间都是没有人使用的,只要您不超过栈空间的范围(栈空间大小的默认值好像是8MB,不过一般的编译器都能设置这个值),你就可以访问这里面的任何一个地址。如果你像下面那么写,也没有任何问题,编译器也不会有任何抱怨,也能得到正确的值:
int mystrlen(char *string)
{
*(long *)(&string - sizeof(char *) - 400) = (long)string;
while(*string++);

return ((long)string - *(long *)(&string - sizeof(char *) - 400) - 1);
}
不过,你得注意的是减去的这个值必须是地址宽度(4个字节)的整数倍。

以上是俺的一点拙见,欢迎探讨。

另外,纠正一下楼上几位朋友的小错误。
栈空间里任何地址和内存都是静态的,所以对于当前进程来说,他们都是可读写的,不存在非法访问,所以才会出现缓冲区溢出的漏洞,会被那些hacker抓住,夺取系统的管理权限;
而堆里的内存如果在没有被分配出来的情况下,才会出现非放访问。如果您了解进程空间的布局,您就不会犯这个错误了。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-04-29 17:13 by Uniker
这个好暴力~~~

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-07-30 05:47 by hoodlum1980
其实它只是利用栈顶的空间去“偷偷”使用栈顶的空间,是“相对安全的”,根据cpu体系而定,栈是向(esp减小)方向增长的。所以减去多少的关键是必须保证这个变量的位置在“安全区域”,当然减的越大越安全(在没有stack overflow的前提下);因为参数上面可能是调用函数指令的下一条指令的地址,还有一些寄存器的值,这里int类型的指针减8,相当于在参数基础上向上跨越32个字节;所以如果你减的太少,可能会访问到栈内数据,那就是非法访问。如果减的很多,就会处于“栈外”,那样就是安全的。

# re: 群里的一道吐血题目,不过让我挺感慨的,发出来与大家分享  回复  更多评论   

2010-07-30 06:01 by hoodlum1980
另外我还觉得前面网友的回复中:
“栈空间里任何地址和内存都是静态的,所以对于当前进程来说,他们都是可读写的,不存在非法访问,。。。:”
这句话值得商榷。
栈是属于线程的,而不是属于“进程”。即每个线程有自己独立的栈,在创建线程使可以制定栈的大小,根据MSDN说法如果不制定由系统默认为1MB,受虚拟内存限制所以这种情况下最多可以创建大约2028线程(可以减小栈的大小来创建更多) 。

所以每个线程有自己独立的栈;这样在多线程编程的时候尤其需要注意,不能把线程的栈上地址用于线程间通讯。例如线程A把它的栈上的地址通信给线程B,如果这时候线程A已经自然退出,就会发生非法内存访问。切记。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理