Author: fighternan
PCIe Sysfs
Posted on
My desktop Put them together, we have 1. Decoding the Address (Fully Qualified Domain BDF) When you see an address like 0000:61:00.1 (your GPU’s HDMI Audio Controller), the kernel is using a highly structured coordinate system [1]: 0000:61:00⋅1 Segment Your Value Hardware Translation Domain 0000 The Virtual Segment. Standard desktop PCs usually have only one domain (0000),…
PCIe Basics
Posted on
1. The Evolutionary Leap: From PCI to PCIe In the 1990s and early 2000s, motherboards relied on PCI and PCI-X (PCI Extended). These were shared parallel buses, meaning multiple devices were connected to the same set of physical wires. The Parallel Bottleneck While intuitive, parallel buses hit a hard physical limit as clock speeds increased: The PCIe Paradigm Shift (2003)…
Bit-banging
Posted on
Bit-banging is a slang term in embedded systems and computer engineering for a technique where software directly controls the state of a general-purpose input/output (GPIO) pin to emulate a hardware communication protocol or signal [1]. Instead of relying on dedicated onboard hardware peripherals (like a built-in SPI, I2C, UART, or PWM controller), the CPU manually toggles a digital…
Bazel: select
Posted on
Think of select() as a conditional expression that lives inside your build rules. It functions exactly like a switch or if/else statement in a programming language, but it operates during the “analysis phase” of a Bazel build. See the other post for constraint_setting and constraint_values 1. The Core Purpose When you build code, you often…
Bazel: platforms
Posted on
Summary Table Concept What it is Analogy Constraint Setting A property category “Vehicle Type” Constraint Value A specific option “Car”, “Truck”, “Motorcycle” Platform A group of settings “Vehicle configured for highway use” (Car + 4 Tires) The Core Concepts To understand how they relate, think of them in terms of a property-based system: Example: Defining…
sysfs-USB
Posted on
USB Controller Two physical USB controller chips (or two controller blocks inside your CPU/System-on-Chip). Each of those physical chips is responsible for generating two logical root hubs: Device Naming Breaking down 1-1.1.5 Let’s use one of the deeper entries from your previous log (1-1.1.5) to see exactly how the dots build the physical address: Think…
C++ 20 Features
Posted on
Coroutines Coroutines are special functions that can have their execution suspended and resumed. To define a coroutine, the co_return, co_await, or co_yield keywords must be present in the function’s body. C++20’s coroutines are stackless; unless optimized out by the compiler, their state is allocated on the heap. Designated initializers Formatting library Combine the simplicity of printf with the type-safety of iostream. Uses braces…
C++ 17 Features
Posted on
std::string_view std::optional A common use case for optional is the return value of a function that may fail. std::filesystem
快带 2025/02
Posted on
WordPress Docker Autostart
Posted on
VM Container
Analyze Coredumps in Yocto
Posted on
Got a coredump Let’s say a daemon got a segmentation fault. Dump the core and SCP it form the machine to your workstation. Prepare new workspace Create a brand new workspace and copy require files over. Compile GDB Depending on your target machine, build the corresponding cross GDB. If you hit python issue, build GDB…
横打心得 2024/10
Posted on
记录一下最近横打的一些心得 最新配置: 樊振东ALC + 正手Tenergy 05 2.1 MM + 反手Tenergy 05 FX 1.9 MM.
Use Span to Avoid Vector of Pointers
Posted on
Consider the above code. PrintStructs will not copy structs at all but still guarantee the constness of MyStruct Constness is especially important. Consider the following awkward situation when you deal with vector of pointers.
Let’s Encrypt SSH
Posted on
This post is based on this post “Containerized WordPress, Migration, and SSL”. I found it a hassle to install and refresh certificates every year (now it’s 90 days!). I want to set up an automated job, which requests to a root CA and installs certs automatically. Let’s encrypt is a free trusted CA. This post…
Do not return const reference
Posted on
Unless you really need to expose a read-only reference to clients (rare). Thread safety is also a problem
String Utilities
Posted on
Eulerian Path
Posted on
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. We have the following properties for undirected graph, An undirected graph has an Eulerian cycle if and only if every vertex has even…
Improve WordPress Performance
Posted on
This post summarized my recent attempt to improve the performance of my website. This post will be updated from time to time. Recently, I got a Black Friday deal at my previous server provider. I chose their new plan and migrated my website from Germany to the United States. I’ve noticed that the latency increased…
The Manacher’s Algorithm Template
Posted on
The Manacher algorithm is a linear algorithm to calculate the total number of palindromic substring of the given string (also the longest palindromic substring). The problem has other solutions, including O(n^2) dynamic programming and O(nlogn) rolling hash + binary search result. Reference https://cp-algorithms.com/string/manacher.html
Binary Exponentiation Template
Posted on
The recursion version is not slower than the while loop version when it is o2 optimized or above. See https://godbolt.org/z/E9jYefrKG.
Reservoir Sampling
Posted on
Given an infinite stream (or a finite sequence of size n), choose k numbers randomly.
Fisher–Yates Shuffle
Posted on
Generating a random permutation of a finite sequence. O(n^2) The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Write down the numbers from 1 through N. Pick a random number k between one and the number of unstruck numbers remaining (inclusive). Counting from the low end, strike out the kth number not…
Whether Should We Call std::move on std::unique_ptr
Posted on
If a function takes a std::unique_ptr<>, that means it takes ownership of the argument. Callers need to use std::move() to indicate that they’re passing ownership if the object being passed is not a temporary: If a function returns a std::unique_ptr<>, that means the caller takes ownership of the returned object. Usage of std::move() while returning an object is only needed if the return type of…
Modular Multiplicative Inverse
Posted on
If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it. Binary Exponentiation Given a and kMod, we can get a^-1 in O(logkMod) time. Dynamic Programming This solves…
LCA (Binary Lifting) Template
Posted on
Rolling Hash Template
Posted on
With a Prime Modular 2^64 as a Modular Two Hash Functions
Segment Tree Template
Posted on
Range Update Index Update
Prime Factorization
Posted on
The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on which, we can do prime factorization in O(logn) time.
Prime Numbers
Posted on
Prime Numbers in [1, n] The naive method takes O(n^1.5)) time. We could use the famous Sieve of Eratosthenes algorithm.
Sliding Window Concepts
Posted on
The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest subarray whose sum is no less than K. A Naive Idea The problem is straightforward if, for every right index, we could find the rightmost left index so that the window has sum >= K….
Minimum Spinning Tree
Posted on
Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…
Eulerian Path
Posted on
Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices). An Eulerian cycle is a Eulerian path that starts and ends on the same vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its…
Boyer–Moore Majority Vote
Posted on
Summary No one is supposed to invent the Boyer–Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here. Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt. Several good points here to mention,…
Pimpl (Opaque Pointers)
Posted on
Summary Pimpl is used to hide implementation details for library consumers. It hides headers, data members, as well as private functions. Note that ~foo() has to be defined after foo::impl gets fulfilled. This is a requirement from unique_ptr: std::unique_ptr may be constructed for an incomplete type T, such as to facilitate the use as a handle in…
Lowest Common Ancestor
Posted on
Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time….
Modular Multiplicative Inverse Concepts
Posted on
Summary Given a modular MOD, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse. To calculate b_, we could use Fermat’s little theorem. If mod is a prime number, we have If we use Binary Exponentiation technique, we could calculate b_ efficiently.
Quick Select & Quick Sort
Posted on
Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance. Quick Sort is an unstable sort. It has amortized…
Shortest Path
Posted on
Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use. Floyd-Warshall Shortest paths (multiple sources) in such graphs that: It is actually a DP problem. We define alg[k][x][y] as the shortest path from x to y using the…
Calculator
Posted on
Summary There are a number of questions in the form that given a string, evaluate the value of it. These questions can be all solved by the routine Infix Notation to Reverse Polish Notation and Evaluate Reverse Polish Notation.
Bit Manipulation Tricks
Posted on
Summary Bit manipulation is all about tricks. bitset is also a common data structure in set problems. Details Bitwise Not Flip Last Set Bit The last set bit is the rightmost set bit. i&(i-1) does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT). (i-1) flips all the bits…
Pure Geometry
Posted on
LC 1453. Maximum Number of Darts Inside of a Circular Dartboard Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary. When dist(p0, p1)>2r, there will be 0 circles. The difficulty is how to get the center of the circle in clean…
DP in Linear Structures (Extra States)
Posted on
Summary In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained. The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index…
Monotonic Queue Concepts
Posted on
Summary Usually, the monotonic queue can be used in the following situations. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest…
DP in Intervals (Break on Boundaries)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is usually reduced to alg[i+1,j], alg[i,j-1], or alg[i+1,j-1] according to the properties of boundaries i and j.
DP in Intervals (Extra States)
Posted on
Summary In this category, given a range alg[i,j], the subproblem is not self contained. To make the subproblem independent to outer ranges, some extra states need to be added.
DP in Intervals (Break in Middle)
Posted on
Summary In this category, given a range alg[i,j], we need to identify a middle point k and change the problem into alg[i,k] and alg[k+1, j]. Details LC 375. Guess Number Higher or Lower II Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually…
Sliding Window & Monotonic Queue
Posted on
Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…
Rolling Hash
Posted on
Summary Rolling hash is a common technique to compare if two substrings are equal or not. Given O(n) preprocessing time, the comparison becomes O(1) at the best case. OJ Details We use two large coprime numbers for base and for mod. We use a polynomial to calculate the hash value. Typical values are and …
Combination & Permutation & DP Counting
Posted on
Summary A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations. Some typical rules and corresponding solutions are listed below. At most x same consecutive elements; the solution is to use a dimension to record the consecutive…
Monotonic Queue in DP
Posted on
Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…