strlen 老瓶裝新酒

来源:https://www.cnblogs.com/life2refuel/archive/2020/05/29/12983832.html
-Advertisement-
Play Games

前言 - strlen 概述 無意間掃到 glibc strlen.c 中代碼, 久久不能忘懷. 在一無所知的編程生涯中又記起點點滴滴: 編程可不是兒戲 ❀, 有些難, 也有些不捨. 隨軌跡一同重溫, 曾經最熟悉的 strlen 手感吧 ~ /* Copyright (C) 1991-2020 Fr ...


前言 - 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 ([email protected]),
   with help from Dan Sahlin ([email protected]);
   commentary by Jim Blandy ([email protected]).

   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) - 1)) != 0;
       ++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) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    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) != 0)
    {
      /* 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 - 1);

      if (cp[0] == 0)
        return cp - str;
      
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

 

正文 - 思考和分析

1. unsigned long int 位元組多大 4 位元組, 8 位元組 ? 

  unsigned long int longword, himagic, lomagic;

 

long 具體多長和平臺有關, 例如大多數 linux , x86 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) - 1)) != 0;
       ++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) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    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) != 0)
    {

 

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  128 =< x <= 255
longword     : 0XXX XXXX  0 < x < 128
longword     : 0000 0000  x = 0

第一種 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 版本去思考和分析. 有興趣可以自行查閱更多.  隨口就來  ~ 做人嘛開心最重要 ~ 千錘百煉芮成鋼 ~ 哈哈哈

 

後記 - 展望與生活

  錯誤是難免的, 歡迎指正和交流 ~ 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 萬丈高樓平地起,改變世界重 Hello World 開始,跨出今天一小步,邁向禿頂一大步…… 一.Visual Studio 創建項目 在前面文章介紹了 Visual Studio 下載和安裝 ,刀已經磨好了,就差殺豬了,打開 Visual Studio,界面如下: 1.選擇 :文件 -> 新建 - ...
  • Python--flask使用 SQLAlchemy查詢資料庫最近時間段或之前的數據 博客說明 文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝! 說明 在操作資料庫的時候,有一個需求是展示最近的記錄,就需要使用查詢最近幾天的數據 思路 獲取 ...
  • ​​​​​​​​ 害,這年頭演算法真的不好學,但是筆試面試又非常愛考,那咋辦呢?我來給你推薦幾本演算法學習好書吧,都是我當年秋招複習時用的,演算法導論什麼的都給我吃灰去吧!! 演算法書單 ​ 演算法圖解 黃小斜的推薦語:這本書太適合入門了,特別是對於電腦非科班的我來說,用它來學演算法的感覺非常酸爽,首先是圖解 ...
  • leetcode-9. 迴文數。 判斷一個整數是否是迴文數。迴文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。 示例 1: 輸入: 121 輸出: true 示例 2: 輸入: -121 輸出: false 解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是 ...
  • ​ 之前寫過很多次關於Java學習指南、Java技術路線圖的文章。但是總還是有小伙伴來問我,Java怎麼學,項目怎麼做,資源怎麼找,真是讓人頭禿。 於是這次黃小斜決定來一波狠的,把所有這些內容都整理起來,做成一份非常硬核的Java學習指南+路線圖,一篇文章搞定Java學習,360度無死角(可能)如果 ...
  • ORM 1. 資料庫配置 配置使用sqlite3,mysql,oracle,postgresql等資料庫 sqlite3資料庫配置 DATABASES = { 'default': { # 預設使用的資料庫引擎是sqlite3,項目自動創建 'ENGINE': 'django.db.backends ...
  • leetcode-8. 字元串轉換整數 (atoi)。 請你來實現一個 atoi 函數,使其能將字元串轉換成整數。 首先,該函數會根據需要丟棄無用的開頭空格字元,直到尋找到第一個非空格的字元為止。接下來的轉化規則如下: 如果第一個非空字元為正或者負號時,則將該符號與之後面儘可能多的連續數字字元組合起 ...
  • 背景 隊列[Queue]:是一種限定僅在表頭進行刪除操作,僅在表尾進行插入操作的線性表;即先進先出(FIFO-first in first out):最先插入的元素最先出來。 本文通過編碼實現鏈式隊列類,並模擬一個有趣的應用,能夠幫助我們對鏈式隊列有更深度的理解。 基本概念 結點 每個元素,除了存儲 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...