2022年10月10日 星期一

MD5 筆記

MD5 Intro

MD5 訊息摘要演算法(英語:MD5 Message-Digest Algorithm),一種被廣泛使用的密碼雜湊函式,可以產生出一個128位元(16個字元(BYTES))的雜湊值(hash value),用於確保資訊傳輸完整一致。(節自wiki)

簡易 MD5 工具 : md5sum

基本上 Unix, Linux 的作業系統都有預設 md5sum
  • md5sum 用法
        # pipe
        $ echo "123" | md5sum
        ba1f2511fc30423bdbb183fe33f3dd0f  -
    
        # 讀檔
        $ md5sum .gitignore
        247bc32fd24d78844194917cb32d556a  .gitignore
    
        # check
        $ md5sum .gitignore > tmp.md5
        $ md5sum -c tmp.md5
        .gitignore: OK
    
        # pipe check
        $ echo "247bc32fd24d78844194917cb32d556a .gitignore" | md5sum -c
        .gitignore: OK
    

openssl/evp.h

The EVP digest routines are a high level interface to message digests (節自 Linux man page)。這裡註記一下 EVP 大概是代表 Envelope。雖然現在已經被改掉,但以前的 openssl/evp.h 的 #ifndef 是 HEADER_ENVELOPE_H。
  • evp 大概的流程
        #include <stdio.h>
        #include <string.h>
        #include <openssl/evp.h>
    
        int main(int argc, char *argv[])
        {
            EVP_MD_CTX *mdctx;
            const EVP_MD *md;
            char mess1[] = "Test Message\n";
            char mess2[] = "Hello World\n";
            unsigned char md_value[EVP_MAX_MD_SIZE];
            unsigned int md_len, i;
    
            if (argv[1] == NULL) {
                printf("Usage: mdtest digestname\n");
                exit(1);
            }
    
            OpenSSL_add_all_algorithms(); // 有可能有些 algo 沒有 load, ex. RSA-SHA1
            md = EVP_get_digestbyname(argv[1]);
            if (md == NULL) {
                printf("Unknown message digest %s\n", argv[1]);
                exit(1);
            }
    
            mdctx = EVP_MD_CTX_new();
            EVP_DigestInit_ex(mdctx, md, NULL); // _ex() 較有效率, 以前的 code 可能是 EVP_DigestInit()
            EVP_DigestUpdate(mdctx, mess1, strlen(mess1));
            EVP_DigestUpdate(mdctx, mess2, strlen(mess2));
            EVP_DigestFinal_ex(mdctx, md_value, &md_len);
            EVP_MD_CTX_free(mdctx);
    
            printf("Digest is: ");
            for (i = 0; i < md_len; i++)
                printf("%02x", md_value[i]);
            printf("\n");
    
            exit(0);
        }
    
參考資料 :
1.MD5 wiki
2.MD5SUM wiki
3.linux man page
4.stackoverflow

2022年10月9日 星期日

讀取 Linux file info (stat)

讀取 Linux 的檔案資訊

Linux 的檔案有很多資訊,即使只用到檔案大小也是很方便。

stat

  • struct stat
    stat 的資料結構
        #include <sys/stat.h>
    
        struct stat {
            dev_t     st_dev;         /* ID of device containing file */
            ino_t     st_ino;         /* Inode number */
            mode_t    st_mode;        /* File type and mode */
            nlink_t   st_nlink;       /* Number of hard links */
            uid_t     st_uid;         /* User ID of owner */
            gid_t     st_gid;         /* Group ID of owner */
            dev_t     st_rdev;        /* Device ID (if special file) */
            off_t     st_size;        /* Total size, in bytes */
            blksize_t st_blksize;     /* Block size for filesystem I/O */
            blkcnt_t  st_blocks;      /* Number of 512B blocks allocated */
    
            /* Since Linux 2.6, the kernel supports nanosecond
                precision for the following timestamp fields.
                For the details before Linux 2.6, see NOTES. */
    
            struct timespec st_atim;  /* Time of last access */
            struct timespec st_mtim;  /* Time of last modification */
            struct timespec st_ctim;  /* Time of last status change */
    
            #define st_atime st_atim.tv_sec      /* Backward compatibility */
            #define st_mtime st_mtim.tv_sec
            #define st_ctime st_ctim.tv_sec
        };
    
  • struct stat
    讀取檔案 (這裡讀 .gitignore)
        #include <stdio.h>    // for printf
        #include <time.h>     // for ctime
        #include <sys/stat.h>
    
        int main()
        {
            struct stat st;
            // 0 success, -1 failed
            // error code: errno
            if(stat(".gitignore", &st) == -1){
                return -1;
            }
            printf("I-node number:             %ld\n", (long) st.st_ino);
            printf("Mode:                      %lo (octal)\n", (unsigned long) st.st_mode);
            printf("Link count:                %ld\n", (long) st.st_nlink);
            printf("Ownership:                 UID=%ld   GID=%ld\n", (long) st.st_uid, (long) st.st_gid);
            printf("device containing file id: %ld\n", (long) st.st_dev);
            printf("device id:                 %ld\n", (long) st.st_rdev);
            printf("File size:                 %lld bytes\n", (long long) st.st_size);
            printf("Preferred I/O block size:  %ld bytes\n", (long) st.st_blksize);
            printf("Blocks allocated:          %lld\n", (long long) st.st_blocks);
            printf("Last status change:        %s", ctime(&st.st_ctime));
            printf("Last file access:          %s", ctime(&st.st_atime));
            printf("Last file modification:    %s", ctime(&st.st_mtime));
            return 0;
        }
    
        I-node number:             20057552
        Mode:                      100664 (octal)
        Link count:                1
        Ownership:                 UID=1000   GID=1000
        device containing file id: 66306
        device id:                 0
        File size:                 16 bytes
        Preferred I/O block size:  4096 bytes
        Blocks allocated:          8
        Last status change:        Tue Mar 29 14:03:01 2022
        Last file access:          Sun Oct  9 19:02:52 2022
        Last file modification:    Thu Jun 17 10:20:57 2021
    
參考資料 :
1.Linux manual page
2.程式人生

2022年9月25日 星期日

vscode 刪除空格 (Remove trailing spaces)

使用 vscode 自動刪除空格的原因

當你上 code 時,有 reviewer 看你的程式碼時,通常會用 meld 等軟體 review。當你的程式碼加了多餘的空格時,都會被這些程式碼 highlight,使得 reviewer 在查看你的程式碼時有一定的不便。

vscode 刪除空格

  • 手動刪除空格 (Remove trailing spaces manually)
    ctrl + alt + p,輸入 trail 你應該就可以看到相關快捷鍵。
  • 自動刪除空格 (Remove trailing spaces automatically)
    setting > 右上角的 open setting (JSON) > 加入以下這行。
        "files.trimTrailingWhitespace": true
    
參考資料 :
1.remove-trailing-spaces-automatically-or-with-a-shortcut

Leet code

最近一直寫 Leetcode,部落格也就荒廢許久,想說突破 200 題來分享一下心得。

Distance question

Leetcode 上有很多問題是關於距離,這裡紀錄下一些有用的數學概念。
  • 平均值 (mean)
    平均值的歐幾里得距離最短 (4*4 + 4*4 < 1*1 + 7*7)
    但相乘值最大 (4*4 > 1*7)
  • 中位數 (median)
    中位數的絕對偏差值最低 (跟其物件的距離之總和最短)
  • 眾數 (mode)
    mode minimizes distance for indicator function (理解不能)
    這個我沒寫過類似的,寫過後我再更新。
參考資料 :
1.leetcode/discuss

2022年1月3日 星期一

Topological Ordering 介紹

Directed Acyclic Graph (DAG) 介紹

不同於 Tree 的無方向、無環,DAG 則是有方向無環。DAG 特性是不斷地前進,有時分流、有時合流,日常常見的 DAG 為族譜、水流以及課程擋修規則

實作

  • Topological Ordering
    拿課程擋修規則為例,有必須先修的課程及後修的課程,將其完整排列出來視為 Topological Ordering。
        // 課程 1 須先修 : None
        // 課程 2 須先修 : 課程 1
        // 課程 3 須先修 : 課程 1, 課程 2
        // 課程 4 須先修 : None
        // 
        // Gragh:
        // 課程 1 -> 課程 2
        //        ↘   ↓
        // 課程 4    課程 3
        //
        // Topological Ordering:
        //  1) 1 2 3 4
        //  2) 4 1 2 3
        //  3) 1 4 2 3
        //  4) 1 2 4 3
        // 兩個都行,只要順序符合規則就好 (按這個例子,課程 4 的排序位置無關緊要)
    
  • Topological Sort ( Kahn's Algorithm  )
    排序時,首先要找到第一個點 (課程 1 或課程 4)。第一個點有一個特別之處,就是沒有人指向他。找出來該第一點後,把其指向的連接也跟著去掉。使下一次課程 2 變為第一個點。以此排序。
        // Gragh:
        //         課程 2
        //           ↓
        // 課程 4   課程 3
    
  • Code
    題目之範例解答
        bool canFinish (int numCourses, vector<vector<int>>& prerequisites) {
    
            // Kahn's Algorithm
            // http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
    
            // adj 紀錄 node 連出去的所有 nodes
            // ref 紀錄 node 被連的次數
            vector<vector<int>> adj(numCourses, vector<int>());
            vector<int> ref(numCourses, 0);
    
            // init
            for (auto&v : prerequisites) {
                ++ref[v[0]];
                adj[v[1]].push_back(v[0]);
            }
    
            // Every loop 都可以找到一個 first node, 需要找出 numCourses 個
            for (int i = 0; i < numCourses; ++i) {
    
                // 一定有 node 的被連的次數為 0, 是為 first node
                // 若所有 node 被連次數都 > 0, 代表有 cycle
                int head = 0;
                while (head < numCourses && ref[head] != 0) ++head;
                if (head == numCourses) return false;
    
                // 找過的 first node 要刪除, 設為 -1
                // 把這次的 first node 所連出去 nodes 的 被連次數(ref) 減一
                ref[head] = -1;
                for (auto & n : adj[head]) --ref[n];
            }
    
            return true;
        }
    
參考資料 :
1.leetcode-problem-course-schedule
2.http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html

Popular Posts