-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
150 lines (105 loc) · 7.37 KB
/
index.html
File metadata and controls
150 lines (105 loc) · 7.37 KB
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
<!DOCTYPE html>
<html lang="zh">
<head>
<meta name="generator" content="Hugo 0.136.5">
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<style type=text/css>body{font-family:monospace;}</style>
<title>cr4c1an</title>
<meta name="description" content="My new homepage or blog">
<link rel="stylesheet" href="/css/style.css">
<link rel="alternate" type="application/rss+xml" href="/index.xml" title="cr4c1an">
</head>
<body>
<header>
=============<br>
== <a href="https://cr4c1an.github.io/">cr4c1an</a> ==<br>
=============
<div style="float: right;">三径就荒，松菊犹存。</div><br>
<p>
<nav>
<a href="/"><b>Start</b></a>.
<a href="/posts"><b>Blog</b></a>.
<a href="/tags"><b>tags</b></a>.
</nav>
</p>
</header>
<main>
<article>
<h1><a href="https://cr4c1an.github.io/posts/%E5%88%86%E5%9D%97-floyd-warshall-%E7%AE%97%E6%B3%95/">分块 Floyd-Warshall 算法</a></h1>
<b><time>2024-12-21 18:37:35</time></b>
<a href="/tags/hpc">HPC</a>
<a href="/tags/algorithm">Algorithm</a>
<a href="/tags/graphtheory">GraphTheory</a>
<a href="/tags/cache_opt">Cache_opt</a>
<div>
<p>普通的 Floyd 算法我们都会了。那么并行化的 Floyd 算法如何呢？</p>
<h2 id="朴素并行化">朴素并行化</h2>
<p>考虑一份经典的 Floyd 代码：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-cpp" data-lang="cpp"><span style="display:flex;"><span><span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> k <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; k <span style="color:#f92672"><=</span> N; k<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; i <span style="color:#f92672"><=</span> N; i<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; j <span style="color:#f92672"><=</span> N; j<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> dis[i][j] <span style="color:#f92672">=</span> min(dis[i][j], dis[i][k] <span style="color:#f92672">+</span> dis[k][j]);
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><p>显然我们可以将第三层循环展开，用 SIMD 优化之。或者，第二、三层循环都可以直接 omp parallel。（请读者自行证明第二层循环也可以，因为任意 <code>dis[k][j]</code> 不会被一个比当前 <code>i</code> 更小的 <code>i1</code> 在这一轮的 <code>k</code> 上以 <code>dis[i1][j]</code> 的方式更新）这里给出第三层循环 omp parallel for 的代码：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-cpp" data-lang="cpp"><span style="display:flex;"><span><span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> k <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; k <span style="color:#f92672"><=</span> N; k<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> <span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; i <span style="color:#f92672"><=</span> N; i<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> <span style="color:#75715e">#pragma omp parallel for
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span> <span style="color:#66d9ef">for</span>(<span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> <span style="color:#ae81ff">1</span>; j <span style="color:#f92672"><=</span> N; j<span style="color:#f92672">++</span>) {
</span></span><span style="display:flex;"><span> dis[i][j] <span style="color:#f92672">=</span> min(dis[i][j], dis[i][k] <span style="color:#f92672">+</span> dis[k][j]);
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span> }
</span></span><span style="display:flex;"><span>}
</span></span></code></pre></div><p>注意到 <code>dis[i][k]</code> 等内存访问比较花费时间，编译器没帮你优化好的话，比如在 <code>-O0</code> 下，性能会不佳。可以利用一些临时变量辅助，减少 <code>dis[i][k]</code> 的寻址时间。这里就不贴代码了。</p>
<a href="https://cr4c1an.github.io/posts/%E5%88%86%E5%9D%97-floyd-warshall-%E7%AE%97%E6%B3%95/">Read more...</a>
</div>
</article>
<article>
<h1><a href="https://cr4c1an.github.io/posts/2024-11-09-javascript%e5%8e%9f%e5%9e%8b%e6%b1%a1%e6%9f%93%e6%bc%8f%e6%b4%9e/">Javascript原型污染漏洞</a></h1>
<b><time>2024-11-09 00:41:35</time></b>
<a href="/tags/ctf">CTF</a>
<a href="/tags/web">web</a>
<a href="/tags/javascript">JavaScript</a>
<a href="/tags/node.js">node.js</a>
<div>
<h1 id="javascript原型污染漏洞">Javascript原型污染漏洞</h1>
<p>js 里的对象可以简单地理解成是其原型（prototype）的一个实例。由于历史原因，所有的对象都有一个__proto__属性。
对于没有任何继承关系的对象，他的原型是 Object。
假设一个对象叫作 ori，一个 tar，那么当</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-javascript" data-lang="javascript"><span style="display:flex;"><span><span style="color:#a6e22e">ori</span>[<span style="color:#e6db74">"__proto__"</span>].<span style="color:#a6e22e">att</span> <span style="color:#f92672">=</span> <span style="color:#e6db74">"test"</span>
</span></span></code></pre></div><p>时，访问 <code>tar.att</code> 的结果是，由于tar.att 属性不直接存在，所以找其原型，故其值为 “test”。
只要我们获得了对 ori 的修改权限，我们就可以间接给 tar 添加属性。
以上。</p>
</div>
</article>
<article>
<h1><a href="https://cr4c1an.github.io/posts/hello_world/">Hello, world</a></h1>
<b><time>2024-11-02 11:17:17</time></b>
<a href="/tags/%E9%97%B2%E8%B0%88">闲谈</a>
<div>
<p>你好，世界。总之折腾了挺久终于把这个博客给部署上了 github.io，作为我的个人博客，希望大家看得开心。</p>
</div>
</article>
<article>
<h1><a href="https://cr4c1an.github.io/posts/idn/">IDA 基础使用</a></h1>
<b><time>2024-11-02 11:17:17</time></b>
<a href="/tags/ctf">CTF</a>
<a href="/tags/ida">IDA</a>
<a href="/tags/reverse">Reverse</a>
<div>
<p>TODO.</p>
</div>
</article>
<div>
1 of 1
</div>
</main>
<footer>
<p>© 2024 <a href="https://cr4c1an.github.io/"><b>copyleft</b></a>.
</p>
</footer>
</body>
</html>