strlen 老瓶装新酒

前言 - strlen 概述

　　无意间扫到 glibc strlen.c 中代码, 久久不能忘怀. 在一无所知的编程生涯中又记起点点滴滴:

编程可不是儿戏 ❀, 有些难, 也有些不舍. 随轨迹一同重温, 曾经最熟悉的 strlen 手感吧 ~

/* Copyright (C) 1991-2020 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   Written by Torbjorn Granlund (tege@sics.se),

   with help from Dan Sahlin (dan@sics.se);

   commentary by Jim Blandy (jimb@ai.mit.edu).

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <https://www.gnu.org/licenses/>.  */

#include <string.h>

#include <stdlib.h>

#undef strlen

#ifndef STRLEN

# define STRLEN strlen

#endif

/* Return the length of the null-terminated string STR.  Scan for

   the null terminator quickly by testing four bytes at a time.  */

size_t

STRLEN (const char *str)

{

  const char *char_ptr;

  const unsigned long int *longword_ptr;

  unsigned long int longword, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.

     Do this until CHAR_PTR is aligned on a longword boundary.  */

  for (char_ptr = str; ((unsigned long int) char_ptr

            & (sizeof (longword) - )) != ;

       ++char_ptr)

    if (*char_ptr == '\0')

      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,

     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits

     the "holes."  Note that there is a hole just to the left of

     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111

     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.

     The 0-bits provide holes for carries to fall into.  */

  himagic = 0x80808080L;

  lomagic = 0x01010101L;

  if (sizeof (longword) > )

    {

      /* 64-bit version of the magic.  */

      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */

      himagic = ((himagic << ) << ) | himagic;

      lomagic = ((lomagic << ) << ) | lomagic;

    }

  if (sizeof (longword) > )

    abort ();

  /* Instead of the traditional loop which tests each character,

     we will test a longword at a time.  The tricky part is testing

     if *any of the four* bytes in the longword in question are zero.  */

  for (;;)

    {

      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != )

    {

      /* Which of the bytes was the zero?  If none of them were, it was

         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - );

      if (cp[] == )

        return cp - str;

      if (cp[] == )

        return cp - str + ;

      if (cp[] == )

        return cp - str + ;

      if (cp[] == )

        return cp - str + ;

      if (sizeof (longword) > )

        {

          if (cp[] == )

        return cp - str + ;

          if (cp[] == )

        return cp - str + ;

          if (cp[] == )

        return cp - str + ;

          if (cp[] == )

        return cp - str + ;

        }

    }

    }

}

libc_hidden_builtin_def (strlen)

正文 - 思考和分析

1. unsigned long int 字节多大 4 字节, 8 字节 ?

  unsigned long int longword, himagic, lomagic;

long 具体多长和平台有关, 例如大多数 linux , x84 sizeof (long) = 4, x64 sizeof (long) = 8.

window x86, x64 sizeof (long) = 4. (2020年05月28日), C 标准保证 sizeof(long) >= sizeof (int)

具体多少字节交给了实现方.

2. ((unsigned long int) char_ptr & (sizeof (longword) - 1)) 位对齐 ?

  /* Handle the first few characters by reading one character at a time.

     Do this until CHAR_PTR is aligned on a longword boundary.  */

  for (char_ptr = str; ((unsigned long int) char_ptr

            & (sizeof (longword) - )) != ;

       ++char_ptr)

    if (*char_ptr == '\0')

      return char_ptr - str;

起始的这些代码的作用是, 让 chart_ptr 按照 sizeof (unsigned long) 字节大小进行位对齐.

这涉及到多数计算机硬件对齐有要求和性能方面的考虑等等(性能是主要因素).

3. himagic = 0x80808080L; lomagic = 0x01010101L; what fuck ?

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits

     the "holes."  Note that there is a hole just to the left of

     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111

     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.

     The 0-bits provide holes for carries to fall into.  */

  himagic = 0x80808080L;

  lomagic = 0x01010101L;

  if (sizeof (longword) > )

    {

      /* 64-bit version of the magic.  */

      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */

      himagic = ((himagic << ) << ) | himagic;

      lomagic = ((lomagic << ) << ) | lomagic;

    }

  if (sizeof (longword) > )

    abort ();

  /* Instead of the traditional loop which tests each character,

     we will test a longword at a time.  The tricky part is testing

     if *any of the four* bytes in the longword in question are zero.  */

  for (;;)

    {

      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != )

    {

3.1 (((longword - lomagic) & ~longword & himagic) != 0) ? mmp ?

可能这就是艺术吧. 想到这个想法的, 真是个天才啊! 好巧妙. 哈哈哈. 我们会分两个小点说明下.

首次看, 感觉有点萌. 我这里用个简单的思路来带大家理解这个问题. 上面代码主要围绕

sizeof (unsigned long) 4 字节和 8 字节去处理得到. 我们简单点, 通过处理 1 字节, 类比递归机制.

搞懂这个公式背后的原理 (ˇˍˇ) ～

/**

 * himagic      : 1000 0000

 * lomagic      : 0000 0001

 * longword     : XXXX XXXX

 * /

unsigned long himagic = 0x80L;

unsigned long lomagic = 0x01L;

unsigned long longword ;

随后我们仔细分析下面公式

((longword - lomagic) & ~longword & himagic)

( & himagic ) = ( & 1000 0000) 表明最终只在乎最高位.

longword 分三种情况讨论

longword     : 1XXX XXXX   =< x <=

longword     : 0XXX XXXX   < x <

longword     :    x =

第一种 longword = 1XXX XXXX

那么 ~longword = 0YYY YYYY 显然 ~ longword & himagic = 0000 0000 不用继续了.

第二种 longword = 0XXX XXXX 且不为 0, 及不小于 1

显然 (longword - lomagic) = 0ZZZ ZZZ >= 0 且 < 127, 因为 lomagic = 1;

此刻 (longword - lomagic) & himagic = 0ZZZ ZZZZ & 1000 0000 = 0 , 所以也不需要继续了.

第三种 longword = 0000 0000

那么 ~longword & himagic = 1111 1111 & 1000 0000 = 1000 000;

再看 (longword - lomagic) = (0000 0000 - 0000 0001) , 由于无符号数减法是按照

(补码(0000 0000) + 补码(-000 0001)) = (补码(0000 0000) + 补码(~000 0001 + 1))

= (补码(0000 0000) + 补码(1111 1111)) = 1111 1111 (快捷的可以查公式得到最终结果),

因而此刻最终结果为 1111 1111 & 1000 0000 = 1000 0000 > 0.

综合讨论, 可以根据上面公式巧妙的筛选出值是否为 0. 对于 2字节, 4 字节, 8 字节, 思路完全相似.

3.2 (sizeof (longword) > 4) ? (sizeof (longword) > 8) 为什么不用宏, 大展宏图呗 ?

宏可以做到多平台源码共享, 无法做到多平台二进制共享. glibc 这么通用项目, 可移植性影响因子

可能会很重. (性能是毒酒, 想活的久还是少喝 ~ )

4. libc_hidden_builtin_def (strlen) ? 闹哪样 ~

理解这个东西, 要引入些场外信息 (不同编译参数会不一样, 这里只抽取其中一条分支解法)

// file : glibc-2.31/include/libc-symbols.h

libc_hidden_builtin_def (strlen)

#define libc_hidden_builtin_def(name) libc_hidden_def (name)

# define libc_hidden_def(name) hidden_def (name)

/* Define ALIASNAME as a strong alias for NAME.  */

# define strong_alias(name, aliasname) _strong_alias(name, aliasname)

# define _strong_alias(name, aliasname) \

  extern __typeof (name) aliasname __attribute__ ((alias (#name))) \

    __attribute_copy__ (name);

/* For assembly, we need to do the opposite of what we do in C:

   in assembly gcc __REDIRECT stuff is not in place, so functions

   are defined by its normal name and we need to create the

   __GI_* alias to it, in C __REDIRECT causes the function definition

   to use __GI_* name and we need to add alias to the real name.

   There is no reason to use hidden_weak over hidden_def in assembly,

   but we provide it for consistency with the C usage.

   hidden_proto doesn't make sense for assembly but the equivalent

   is to call via the HIDDEN_JUMPTARGET macro instead of JUMPTARGET.  */

#  define hidden_def(name)    strong_alias (name, __GI_##name)

/* Undefine (also defined in libc-symbols.h).  */

#undef __attribute_copy__

#if __GNUC_PREREQ (9, 0)

/* Copies attributes from the declaration or type referenced by

   the argument.  */

# define __attribute_copy__(arg) __attribute__ ((__copy__ (arg)))

#else

# define __attribute_copy__(arg)

#endif

利用上面宏定义, 进行展开

libc_hidden_builtin_def (strlen)

|

hidden_def (strlen)

|

strong_alias (strlen, __GI_strlen)

|

_strong_alias (strlen, __GI_strlen)

|

extern __typeof (strlen) __GI_strlen __attribute__ ((alias ("strlen"))) __attribute_copy__ (strlen);

|

extern __typeof (strlen) __GI_strlen __attribute__ ((alias ("strlen"))) __attribute__ ((__copy__ (strlen)));

``

其中 GUN C 扩展语法

　　__typeof (arg) : 获取变量的声明的类型

　　__attribute__ ((__copy__ (arg))) : GCC 9 以上版本 attribute copy 复制特性

　　alias_name __attribute__ ((alias (name))) : 为 name 声明符号别名 alias name.

总结: libc_hidden_builtin_def (strlen) 意思是基于 strlen 符号, 重新定义一个符号别名 __GI_strlen.

(补充资料 strong_alias 注释)

strlen 工程代码有很多种, 我们这里选择一个通用 glibc 版本去思考和分析. 有兴趣可以自行查阅更多.

随口就来 ~ 做人嘛开心最重要 ~ 千锤百炼芮成钢 ~ 哈哈哈

后记 - 展望与生活

　　错误是难免的, 欢迎指正和交流 ~

巴特西