DEV Community: wrongbyte

Introduction to graphs - BFS algorithm

wrongbyte — Thu, 14 Sep 2023 23:33:40 +0000

Imagine we have a game in which the characters can move in a 2D grid, just like the image below:

Now, let's say our character needs to reach the marked square. More importantly, he needs to reach the destination in the shortest path possible, considering that the character can only move one square horizontally or vertically at a time.

How can we solve this problem and find the shortest path? The answer lies on graphs.

Changing the perspective: seeing the grid as a graph

The image above depicts a graph - a visual representation of data or information that consists of nodes (or vertices) connected by edges. Each node represents an entity, while the edges represent relationships or connections between these entities. Graphs can be used to model a wide range of complex systems, such as social networks, transportation networks, computer networks, and more. They are a fundamental data structure in mathematics and computer science, enabling the analysis, visualization, and problem-solving of various real-world scenarios and relationships.

In our problem, a graph is useful to model the grid - a set of coordinated points representing all possible positions of our character. As we are talking about a movement that can only be horizontal or vertical, each square has adjacent squares that the character can move to, provided they meet the condition of being horizontally or vertically adjacent.

Therefore, the grid below

Can be represented by the following graph, in which we can see the nodes and the edges connecting them:

This shift of perspective is the first step to solve our problem; the second step is to write an algorithm to "walk the graph"

Pathfinding algorithms

Finding the shortest path in a graph is a very common problem encountered in various real-life scenarios - think about GPS navigation systems, for example.

For this reason, this type of algorithm has been studied for a long time, and nowadays there are multiple ways to solve the problem of "finding the shortest path." The simplest algorithms are Breadth-First Search (which we'll see in this post) and Depth-First Search. There are also more advanced (and effective) ones such as Dijkstra and A*.

How Breadth-First Search works?

Think about it for a minute: what is the first step to find the shortest path in a maze?

One possible answer is to first map all the possible paths. After all, to find the shortest path, we first need to know which paths are possible, taking into account the character's movement restrictions.

We can narrow down the problem scope by asking, "Which squares can my character move to from the current position, denoted as X?"
This is necessary given that, particularly at the edges of the grid, the character may not be able to move further vertically or horizontally. Furthermore, there could be scenarios where the character's movement should be limited by certain conditions, similar to this Advent of Code problem.

Therefore, let's write a simple function that decides the "available neighbors" (adjacent positions which we can move to), given we are working with coordinates, represented by cartesian points like below:



pub struct Coord {
    x: usize,
    y: usize,
}



pub fn neighbors(grid: &Grid, curr_coord: &Coord) -> Vec<Coord> {
    let deltas: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    let neighbors: Vec<Coord> = deltas
        .into_iter()
        .filter_map(|(dx, dy)| {
            let coord_x = curr_coord.x.checked_add_signed(dx)?;
            let coord_y = curr_coord.y.checked_add_signed(dy)?;

            let neighb_coord = Coord {
                x: coord_x,
                y: coord_y,
            };
            if !grid.in_bounds(&neighb_coord) {
                return None;
            }
            Some(neighb_coord)
        })
        .collect();

    neighbors
}

This function receives the grid as a parameter. The grid is a struct that contains all the points and info such as height and width:



pub struct Grid {
    width: usize,
    height: usize,
    data: Vec<Coord>,
    start_coord: Coord,
    end_coord: Coord,
}

Then, we are going to check all possible four coordinates that are adjacent to the current coordinate. In the code, this is represented by [(-1, 0), (1, 0), (0, -1), (0, 1)], which are the numbers we are going to sum with x and y to verify squares vertically and horizontally adjacent.
Rust provides a method checked_add_signed, which is used here to verify if the sum returns a positive number. For example, if we add 0 + (-1), we would get -1, but here Rust returns None to this operation - which excludes negative (and therefore invalid) coordinates from the neighbors returned by this function.
After excluding possibly negative coordinates, the grid.in_bounds() method checks if the neighbor coordinates are out of grid bounds:



pub fn in_bounds(&self, coord: &Coord) -> bool {
        coord.x < self.width && coord.y < self.height
}

In sum, the general idea in this step is to get the adjacent coordinates from a grid square and return only the valid ones.

However, mapping the available positions for each square is not enough: how do we move from square to square?

Enqueueing the nodes

Walking the graph involves:
1 - Moving to a square
2 - Mapping the available positions from that square
3 - Moving to the next available square

In code, this can be translated to: put the available nodes in a queue, visit each node mapping its neighbors (and putting them in the queue), store the visited nodes and repeat this sequence until the queue is empty.

Visually, we can demonstrate it like this (images from GeeksforGeeks):

We start with an empty queue and an empty array of visited nodes. Once we map the available nodes from that starting point, we populate the queue and mark the start coordinate as visited:

While the queue is not empty, we get the first element from it (that becomes our current node), map their neighbors and add it to the visited array.



    while queue.len() != 0 {
        let curr_node = queue.pop_front().expect("queue is empty");
        let curr_node_neighbors = neighbors(grid, &curr_node, part);
        for neighbor in curr_node_neighbors {
            if !visited.contains(&neighbor) {
                queue.push_back(neighbor);
                visited.push(neighbor);
            }
        }

Once the queue is empty, we know all possible paths have been checked.

All roads lead to Rome

Finding all possible paths our character can walk does not tell us anything about the shortest path to point X. However, we are halfway there.

Since we guarantee that nodes in visited vec are not visited again, no node is visited more than once. This constraint guarantees we don't repeat ourselves checking again paths that lead to nowhere. Additionally, BFS employs a queue data structure to keep track of nodes to visit - which means nodes are enqueued in the order they are discovered, and dequeued in the same order. This "first-in, first-out" (FIFO) behavior ensures that nodes closer to the source are explored before nodes farther away.

Therefore, once BFS reaches the node we are searching for (the destination node), it has essentially found the shortest path in terms of the number of edges.

Finally, to find the shortest path, we can start from the destination node and follow its parent backward through the graph until we reach the source node.

To do so, we keep track of the parent node of each node visited, so that we can reconstruct the path. We can do this using a hashmap, for example, to store coordinates and their respective parents.



let mut coord_parents: HashMap<Option<Coord>, Option<Coord>> = HashMap::new();

And finally, we can add the following logic to recreate the path that leads to the destination node:



if curr_node == end {
    let mut current = Some(end);
    while let Some(current_coord) = current {
        path.push(current_coord);
        current = *coord_parents.get(&current).expect("coord not found");
    }
}

Basically, what this code does is populate a Vec named path, which stores the Coords that correspond to the path from the initial node to the final node. As you can see, this Vec is constructed based on the information of the parent of each node.

Our code becomes roughly like this:



pub fn find_path(grid: &Grid) -> Vec<Coord> {
    let mut queue: VecDeque<Coord> = VecDeque::new();
    let mut visited: Vec<Coord> = Vec::new();
    let mut path: Vec<Coord> = Vec::new();

    let mut coord_parents: HashMap<Option<Coord>, Option<Coord>> = HashMap::new();

    // Populate the initial info
    let start = grid.start_coord;
    let end = grid.end_coord;
    coord_parents.insert(Some(start), None);
    queue.push_back(start);
    visited.push(start);

    while queue.len() != 0 {
        let curr_node = queue.pop_front().expect("queue is empty");
        if curr_node == end {
            // We reached the end node, now we reconstruct the path
            let mut current = Some(end);
            while let Some(current_coord) = current {
                path.push(current_coord);
                current = *coord_parents.get(&current).expect("coord not found");
            }
        }
        let curr_node_neighbors = neighbors(grid, &curr_node);
        for neighbor in curr_node_neighbors {
            if !visited.contains(&neighbor) {
                queue.push_back(neighbor);
                visited.push(neighbor);
                coord_parents.insert(Some(neighbor), Some(curr_node));
            }
        }
    }
    path
}

BFS definitely is not the standard for pathfinding nowadays, since it is a lot less efficient than more advanced algorithms, such as A*. However, understanding how BFS works provide us with very useful insights about the importance of graphs and how they can be applied in Computer Science.

Beginner's guide to Rust references

wrongbyte — Sat, 05 Aug 2023 16:32:09 +0000

You probably know that this code does not compile

fn main() {
    let my_vec = vec![1, 2, 3];
    let my_other_vec = my_vec;
    println!("{:?}", my_vec); // error!
}

but this code does:

fn main() {
    let my_number = 1;
    let my_other_number = my_number;
    println!("{:?}", my_number);
}

It happens due to the key principle of Rust language: the ownership system. Two main things happen here:

Vec<T> does not implement the Copy trait, so its value will be moved to my_other_vec and we won't be able to use my_vec after that.
i32 does implement the Copy trait, so its value will be copied to my_other_number, and we can still use the my_number variable.

However, in the real world, we often deal with types that don't implement the Copy trait, and having to move things around multiple times would become a real headache if there was no alternative. But Rust has a way to use values without moving them: borrowing.

fn main() {
    let my_vec = vec![1, 2, 3];
    add_one(&my_vec)
}

fn add_one(v: &Vec<i32>) {
    println!("{:?}", v);
}

If the add_one function were to accept a Vec instead of a &Vec, any vec passed to this function would be moved into it, rendering the original value unusable. Since this is not the behavior we want, our function now accepts a reference to a value, instead of the value itself.

Immutable references (`&T`) - reading a value

The previous snippet shows a scenario in which we need to borrow a value only for reading, without modifying it. Just like variables in Rust, which are immutable unless you put the keyword mut in the declaration, references are also immutable by default.
This behavior guarantees that we do not accidentally change the value, since we are only reading from it. For this reason, we can have as many immutable references as we want - and that's the reason why the type &T is also called a shared reference.

However, the use of immutable references follows some additional rules.
Let's imagine a scenario in which we need to create a Vec<i32> based on another Vec<i32>, but we only have access to the reference pointing to the Vec.

let my_vec_ref: Vec<i32> = &my_vec;

There is a type mismatch here, since my_vec_ref is supposed to be a Vec, not a reference to one. However, there is a solution: Rust provides the "inverse" operator of &: the * operator, which lets us access the value behind a reference!

fn main() {
    let my_vec: Vec<i32> = vec![1, 2, 3];
    let my_vec_ref = &my_vec;
    let another_vec = *my_vec_ref; // oops!
}

... but not to move it.

The code above gives us the following error:

cannot move out of `*my_vec_ref` which is behind a shared reference
move occurs because `*my_vec_ref` has type `Vec<i32>`, which does not implement the `Copy` trait

Alright, we know that Vec<i32> does not implement the Copy trait and stuff, but what is this error actually telling us?

Moving out

The = operator creates an assignment expression. According to Rust docs, an assignment expression moves a value into a specified place.

Things are pretty straightforward when we are dealing with straightforward types, but a reference is what we call an indirection type - a type that has a "layer" between you and the real data. In this case, we can imagine the reference as a wrapper for the data. Due to its immutability, we are not allowed to either change what's inside of it or move what's inside of it. In other words, we can't "move out".
It also implies that we can only move things from values we own, never from values we borrow - which is another way to say the same thing.

Additionally, in Rust the . operator automatically dereferences reference types, causing the same error to happen when we try to do things such as the code below.

struct MyStruct {
    str_vec: Vec<i32>
}

fn main() {
    let strct = MyStruct { str_vec: vec![1, 2, 3]};
    let strct_ref = &strct;
    let my_vec = strct_ref.str_vec; // error!
}

This behavior is useful when talking about methods that take self by reference, ommiting the use of * operator:

struct MyStruct { n: u32 };

impl MyStruct {
    // no need to type (*self).n
    fn method(&self) -> u32 { self.n }
}

let x = MyStruct { n: 12 };
// Here the compiler automatically references self,
// so that there's no need to write (&x).method()
let n = x.method();

The solution

Back to one of our previous examples:

fn main() {
    let my_vec: Vec<i32> = vec![1, 2, 3];
    let my_vec_ref = &my_vec;
    let another_vec: Vec<i32> = *my_vec_ref; // oops!
}

In cases like this, the error messages may contain some misleading instructions, such as the following:

consider borrowing here: `&*my_vec_ref

This is not possible here, since it means assigning a &Vec<i32> to a value that has type Vec<i32>.

Therefore, the solution when this error happens is to clone the value - so that you get a copy from it without moving it.

let another_vec: Vec<i32> = my_vec_ref.clone();

Mutable references (`&mut T`)

Modifying a non-copy value follows the logic of moving or borrowing. You can either move the value in order to modify it, or use a mutable reference (borrow) to do so.
Let's create a function that modifies a value using a &mut T:

fn main() {
    let mut my_vec = vec![1, 2, 3];
    let ref_my_vec = &mut my_vec;
    add_one(ref_my_vec);
    println!("{:?}", my_vec);
}

fn add_one(v: &mut Vec<i32>){
    v.push(1);
}

When we assign a mutable reference to ref_my_vec, it means that this variable points to an existing value, instead of owning a new value. Therefore, modifying ref_my_vec is equivalent to directly modify my_vec. We can say that a mutable reference provides us with write access to a value.
However, since the only way to securely modify a value is to have an unique write access to it (think about data races), Rust does not allow us to have more than one mutable reference to the same value simultaneously.

    let ref_my_vec = &mut my_vec;
    let another_ref = &mut my_vec;
    // cannot borrow `my_vec` as mutable more than once at a time

This is the reason why a mutable reference is also called an unique reference.
Similarly to shared references, Rust also does not allow us to move out of mutable references. In fact, moving out from any kind of reference - mutable or not - is not allowed.

fn main() {
    let mut my_vec: Vec<i32> = vec![1, 2, 3];
    let my_vec_ref = &mut my_vec;
    let another_vec = *my_vec_ref; // oops!
}

cannot move out of `*my_vec_ref` which is behind a mutable reference
move occurs because `*my_vec_ref` has type `Vec<i32>`, which does not implement the `Copy` trait

Mutability with references

What is the difference between `p: &T`, `mut p: &T`, `p: &mut T` and `mut p: &mut T`?

When talking about a variable whose type is a reference, it is important to differentiate what does it mean to change what the reference points to and what our variable points to.
Therefore, you can do the following:

let vec_number = vec![1, 2, 3];
let another_vec = vec![2, 3, 4];
let mut ref_vec = &vec_number;
ref_vec = &another_vec;

Let's see what is happening here.
Although we cannot change the data the ref_vec variable points to, we can make ref_vec point to another data (as long as it has the same type of the data previously assigned).
Therefore, when we put the mut keyword in the left side of an assignment expression, we are telling Rust that we are going to reassign that variable to another value.

Type	Can reassign the variable	Can change the data the variable points to
p: &T	❌	❌
mut p: &T	✅	❌
p: &mut T	❌	✅
mut p: &mut T	✅	✅

Implementing Iterator and IntoIterator in Rust

wrongbyte — Tue, 25 Apr 2023 23:13:22 +0000

Iterators are a powerful tool that allow for efficient iteration over data structures, and they are implemented in many programming languages - including Rust. However, Rust's unique ownership system gives rise to interesting differences in how iterators are implemented and used. In this article, we will explore these differences and delve into Rust's features by creating and implementing the most commonly used iterator traits - Iterator and IntoIterator.

Imagine you have a structure like this:

pub struct Todos {
    pub list: Vec<Todo>,
}

The struct above is a Vec<Todo>, which is a vector of Todos, which have this structure:

pub struct Todo {
    pub message: String,
    pub done: bool,
}

If we wish to iterate over each Todo in this Vec, we could simply use its list property and iterate over its items, right?
But what if we wanted to iterate over Todos itself, without exposing its internal properties?
That's where things start to get interesting...

What is an iterator?

An iterator is a pattern that allows you to go through each element in an iterable sequentially. Iterators are very useful in loops, allowing you to iterate over items in a neat way.
Let's see a loop without and with iterators, in Javascript:

let array = [1, 2, 3, 4];

// without iterators
for (var i = 0; i < array.length; i++) {
    console.log(array[i]);
}

// with iterators; "item" is the iterator
for (item of array) {
    console.log(item)
}

As you can see, they are present in a lot of other languages, as Javascript, Python and so on.

Iterators in Rust

In Rust, similarly with languages such as Python, iterators are lazy. It means that they are effectless unless you iterate over them (a.k.a consume them).

let numbers = vec![1, 2, 3];
let numbers_iter = numbers.iter();

The code above creates an iterator - and does nothing with it.
To use the iterator, we should create a for loop, for example as it follows:

let numbers = vec![1, 2, 3];
let numbers_iter = numbers.iter();

for number in numbers {
    println!("{}", number)
}

There are also other ways which we can use to create iterators. For example, every time we use map() in Rust we are creating an iterator.

Iterators vs Iterables

A vector, as seen before, is an iterable.
It means that we can iterate over them; but more precisely, it means that we can use a Vec to create an Iterator. This is the definition of an iterable - some object with which we can create an Iterator. For example, a Vec<u32> can produce an iterator - but is not an iterator itself.

Creating an Iterator

Okay, let's go back to our Todos struct and see how could we create a way to iterate over its items.
Todos has a field list, which is a Vec<Todos>.
In Rust, Iterator is a trait which has some methods in it, such as next(), which is responsible for taking the next element of the collection and returning it, or returning None if we've already reached the end of the collection. Its implemention looks roughly like this:

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}

Fine. We could, then, create a way to iterate over the elements of the list field of our Todos, writing a custom next() function. The logic for this is simple - we could do something like this, in pseudocode:

function next() {
    if index < list.len() {
        let todo = Some(list[index])
        self.index += 1
        return todo 
    } else {
        return None
    }
}

In the logic above, we check for the index of the element and return it, given its index is less than the list length.
But we have a problem here. Where to store index?

Storing state

That's when the difference between an iterator and an iterable comes into hand.
Translating the pseudocode above, one could implement the next() function in Todos like this, implementing a method from the Iterator trait,

impl<'a> Iterator for Todos {
    type Item = &'a Todo;
    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.list.len() {
            let result = Some(&self.list[self.index]);
            self.index += 1;
            result
        } else {
            None
        }
    }
}

But it would require us to change the structure of our Todos: we would need to add a index field in it to use every time we call next() - which is, every time we iterate over its items through an iterator.

pub struct Todos {
    pub list: Vec<Todo>,
    index: usize,
}

In this logic, we would modify the constructor function in order to always create the struct with index: 0.

pub fn new(list: Vec<Todo>) -> Self {
    Todos { list, index: 0 }
}

However, this approach simply does not feel right...
Storing an index field in your struct is not ideal; the index is used for storing the current state in an iterator, so it should be part of the iterator, not of the struct. This is why we are going to create an iterator type - which is going to store the index property - and implement the Iterator trait for this type.

The iterator is a type that abstracts the logic of iterating over an iterable; it also stores the current state of iteration, such as the index property.

`TodoIterator`

Let's create our iterator then!
First of all, we need to create the type of the iterator:

struct TodosIterator<'a> {
    todos: &'a Todos,
    index: usize,
}

Note the lifetime annotations here.
TodosIterator has a field todos, which references a Todos. As we are dealing with a reference, we need to ensure that this field points to something valid - and here lifetime parameters come at hand. The struct TodosIterator is generic over this lifetime, 'a'.
Basically, we are using this notation to specify that the todos field of the iterator needs to have the same lifetime as the data it is pointing to. This way, we ensure that it cannot reference a Todos struct that has been dropped.

Implementing Iterator for `TodosIterator`

// ps: it could be done using .get() as well, however I wanted to use this approach to make it a bit more clear how Options are returned in this context 
impl<'a> Iterator for TodosIterator<'a> {
    type Item = &'a Todo;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.todos.list.len() {
            let result = Some(&self.todos.list[self.index]);
            self.index += 1;
            result
        } else {
            None
        }
    }
}

Now, we are doing it right.
In the implementation of this trait, we specify the same lifetime used for the struct. It means that the implementation is tied to the lifetime of the struct - which is necessary because we are returning a reference in the next() method.

How to use this iterator?

Now we have already created the TodoIterator struct as well as implemented the Iterator trait for this struct, how do we use it to iterate over Todos?
The answer lies on the iter() method. This method takes a reference of our Todos and uses it to create an iterator, which we can use to iterate!

impl Todos {
    pub fn iter(&self) -> TodosIterator {
        TodosIterator {
            todos: self,
            index: 0,
        }
    }
}

// Now we can iterate:
for todo in todos.iter() {
    println!("{}", todo); // each todo is a &Todo, and is immutable
}

IntoIterator

IntoIterator is a bit different from the Iterator trait. Its single method, into_iter(), returns an iterator over some data and makes it possible to iterate over data in a generic way, regardless of its actual type. It happens because all types that implement IntoIterator can be converted into an iterator.

Let's understand its implementation:

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}

Some important points here:
1 - The Item type parameter is the type of the elements that the iterator will yield.
2 - The IntoIter type parameter is the type of the iterator that will be returned by the into_iter method. This type must implement the Iterator trait, and the type of its Item must be the same as the Item of IntoIterator.
3 - The into_iter method takes self as an argument, meaning it consumes the original object and returns an iterator over its elements.

Ok, how to implement it?
You may think we could reuse the TodosIterator - however, we can't since it takes a &Todos, and we need to take ownership of the iterable. So let's create another iterator that does it:

pub struct TodosIntoIterator {
    todos: Todos
}

The difference between TodosIntoIterator and TodosIterator is that here we are not using a reference, but taking ownership and returning each item itself - that why we also don't need the lifetime annotations anymore. And also there's no index to keep the state, we soon are going to see why.

Following the definition of the trait IntoIterator, we can implement it for Todos:

impl IntoIterator for Todos {
    type Item = Todo;
    type IntoIter = TodosIntoIterator;

    fn into_iter(self) -> TodosIntoIterator {
        TodosIntoIterator { todos: self }
    }
}

However, before doing it, we need to implement Iterator for TodosIntoIterator (remember the type parameters?) to describe how we are going to iterate over it.

impl Iterator for TodosIntoIterator {
    type Item = Todo;

    fn next(&mut self) -> Option<Self::Item> {
        if self.todos.list.len() == 0 {
            return None;
        }
        let result = self.todos.list.remove(0);
        Some(result)
    }
}

This implementation is a bit different from what we've done for TodosIterator. We are taking advantage of the remove() method that exists for Vecs in Rust. This method removes the item at the position n and returns it to us, giving the ownership (which is necessary to return a Todo instead of a &Todo). Due to how this method works, we can always use "0" to return the first element, instead of storing a state and increasing it sequentially.
Using remove also guarantees that we are going to yield each value exactly once while also not keeping values already returned in the state of the iterator.

And now, we are done! These two implementations make it possible for us to iterate over a Todos in two different ways:

By reference (&Todos)

for todo in todo_list.iter() {
    println!("{}", todo);// todo is a &Todo
}

// we can reuse todo_list, since it's not consumed

Taking ownership:

for todo in todo_list {
    println!("{}", todo); // todo is a Todo
}

// we cannot reuse todo_list, since the for loop consumes it

How to deploy a function in Google Cloud with Terraform

wrongbyte — Fri, 03 Feb 2023 16:58:51 +0000

Previously, we've deployed a cloud function in Google Cloud. We have done it through the GCP's command line utility.
Now, we can create and run the same Cloud Function using Terraform.

Why to use Terraform?

When we deployed our function using Google's SDK directly, we had to use a command with several flags that could be grouped together in a deploy.sh script:

gcloud functions deploy $FN_NAME \
    --entry-point=$FN_ENTRY_POINT \
    --runtime=nodejs16 \
    --region=us-central1 \
    --trigger-http \
    --allow-unauthenticated

In this script, we are specifying exactly how we want our cloud function to be. The flags specify the entrypoint, the runtime, region, trigger and etc.

One could say we are describing how our infrastructure should be. Exactly what we could do with infrastructure as code - in this case, using Terraform!

Creating a `main.tf`

The main.tf file is the starting point for Terraform to build and manage your infrastructure.

We can start by adding a provider. A provider is a plugin that lets you use the API operations of a specific cloud provider or service, such as AWS, Google Cloud, Azure etc.

provider "google" {
    project = "project_name"
    region = "us-central1"
}

But let's think about the following scenario: what if you wanted to create a generic template infrastructure that could be reused for different projects other than project_name?
Here it comes the tfvars file: a file in which you can put all your environment variables:

google_project = "project_name"

And now you can use this variable in your main.tf (you also need to add a block telling Terraform you've declared a variable somewhere else):

variable "google_project_name" {}

provider "google" {
    project = "${var.project_name}"
    region = "us-central1"
}

Now, let's start to add the infrastructure specific to our project!

Terraform `resource`s

A Terraform resource is a unit of Terraform configuration that represents a real-world infrastructure object, such as an EC2 instance, an S3 bucket, or a virtual network. In our case, we are going to represent a cloud function.
We define these resources in blocks, where we describe the desired state of the resource - including properties such as the type, name, and other configuration options.

Understanding how state works is important because, every time Terraform applies changes to the infrastructure of our projects, it updates resources to match the desired state defined in the Terraform configuration.

What's inside a `resource`?

Besides the definition previously mentioned, a Terraform resource is - syntatically - a block compound of three parts:

The type of the resource, such as aws_instance or google_compute_instance.
The name of the resource, which must be unique within the Terraform configuration.
Configuration options for the resource (the state, as said before), such as the image ID for an EC2 instance or the bucket name for an S3 bucket.

Alright. We are getting there.
Let's then create the resource block for our Google Cloud Function!

Each resource block has its specific properties. You can find them in the docs of the Terraform provider you are using. For example, here is the docs for the cloud function we'll be creating:
https://registry.terraform.io/providers/hashicorp/google/latest/docs/resources/cloudfunctions_function

We can start by defining a few things, such as the name, description and runtime:

resource "google_cloudfunctions_function" "my_function" {
    name = "my_function"
    description = "the function we are going to deploy"
    runtime = "nodejs16"
}

Note: you may have noticed that we are repeating my_function twice here.
It happens because we have to set a name for the resource - in this case, my_function, which is translated to google_cloudfunctions_function.my_function in Terraform - and we also have to set the value of the name field of the block, which is going to be used by Google - not Terraform - to identify your function.

The source code

However, even though we know these basic properties of our function, where is the source code? In the previous tutorial, Google SDK was able to look into our root directory to find our index.js file. But here, we only have a Terraform file which specifies our desired state, but no mentions at all about where to find the source code for our function. Let's fix it.

Creating a bucket

From the docs, we know we have several ways available to specify in our resource block where to find the source code of our function. Let's do it with a storage bucket.

resource "google_storage_bucket" "source_bucket" {
    name = "function-bucket"
    location = "us-central1"
}

Now we have a bucket, but we also need a bucket object that stores our source code.

resource "google_storage_bucket_object" "source_code" {
    name = "object-name"
    bucket = google_storage_bucket.bucket.name
    source = "path/to/local/file"
}

Note the source field.
Accordingly to the docs, we need to use a .zip file to store the source code (as well as other files such as package.json). We can transform our directory into a zip file using a data "archive_file" block:

data "archive_file" "my_function_zip" {
    type = "zip"
    source_dir = "${path.module}/src"
    output_path = "${path.module}/src.zip"
}

path.module is the filesystem path of the module where the expression is placed.

Therefore, now our main.tf looks like this:

variable "google_project_name" {}

provider "google" {
    project = "${var.google_project_name}"
    region = "us-central1"
}

data "archive_file" "my_function_zip" {
    type = "zip"
    source_dir = "${path.module}/src"
    output_path = "${path.module}/src.zip"
}

resource "google_cloudfunctions_function" "my_function" {
    name = "myFunction"
    description = "the function we are going to deploy"
    runtime = "nodejs16"
    trigger_http     = true
    ingress_settings = "ALLOW_ALL"
    source_archive_bucket = google_storage_bucket.function_source_bucket.name
    source_archive_object = google_storage_bucket_object.function_source_bucket_object.name
}

resource "google_storage_bucket" "function_source_bucket" {
  name = "function-bucket"
  location = "us-central1"
}

resource "google_storage_bucket_object" "function_source_bucket_object" {
  name   = "function-bucket-object"
  bucket = google_storage_bucket.function_source_bucket.name
  source = data.archive_file.my_function_zip.output_path
}

We can deploy! But... There's still some things missing.

Using Google SDK we were able to get the URL of our function - since it has a HTTP trigger. It would be good to get this URL right away.
Also, we needed to set IAM policies to let everyone trigger our function. How to do something similar in Terraform?

We can fix these things by adding two blocks: one which is for IAM policies and another to display the output - an output block.

In Terraform, an output block is used to define the desired values that should be displayed when Terraform applies changes to infrastructure.
If we run terraform plan right now, we can see some properties that will be known once the infrastructure is created. And https_trigger_url is exactly what we are looking for!

output "function_url_trigger" {
    value = google_cloudfunctions_function.my_function.https_trigger_url
}

resource "google_cloudfunctions_function_iam_member" "my_second_fn_iam" {
  cloud_function = google_cloudfunctions_function.my_function.name
  member         = "allUsers"
  role           = "roles/cloudfunctions.invoker"
}

Now, we can run terraform apply and get, as the output, the URL that triggers our function:

And finally, we can trigger it:

Still feel like you missed something? Take a look on the source code for this tutorial: https://github.com/wrongbyte-lab/tf-gcp-tutorial

How to deploy a Cloud Function in Google Cloud

wrongbyte — Mon, 30 Jan 2023 21:48:50 +0000

A cloud function is a single unit of code that can be executed in response to a specific event. In the context of serverless architecture, cloud functions are a way of deploying and running small pieces of code without the need for managing infrastructure. This can greatly simplify the process of building and deploying applications. So, let's learn how to deploy a simple function in Google Cloud Platform.

Every function must have a trigger, which is the specific event that calls the function and makes our application "wake up".
We can have event triggers or HTTP triggers, but I choose to use HTTP triggers for this tutorial.

How to do it, step by step

First, you need to have Google SDK installed in your machine. Once you have it, authenticate to your account using

gcloud auth login

Once you have this basic setup, let's start.

Writing a cloud function

Let's use a javascript function here. I choose to use a HTTP trigger. It means that our function will be triggered every time we receive a HTTP request to the URL assigned to it.

By default, Cloud Functions attempts to load source code from a file named index.js at the root of your function directory. To specify a different main source file, use the main field in your package.json file.

As we are dealing with HTTP triggers, we must create a simple function that runs every time we receive a request:

const myFunction = async (req, res) => {
  const name = req.query.name || "World";
  res.send(`Hello ${name}!`);
};

module.exports = {
    myFunction
}

This is our index.js: nothing but a simple function. Our code here doesn't need to have a complicated structure, but it must have a function entry point, which is the code that is executed when the Cloud Function is invoked.

Deploying

In the code below,

gcloud functions deploy $FN_NAME \
    --entry-point=$FN_ENTRY_POINT \
    --runtime=nodejs16 \
    --region=us-central1 \
    --trigger-http \
    --allow-unauthenticated

The important part is the entry-point flag. It specifies which function is the entry point. Google will lookup in our index.js to find it.

Another interesting flag is the allow-unauthenticated. Without this flag, we would only be able to invoke our function if we made a request using a token from an account that has the roles/cloudfunction.functions.invoker permission.

Note: to successfully use this flag, you need to have the cloudfunctions.functions.setIamPolicy permission, since what --allow-unauthenticated does is basically to set a IAM policy for your cloud function, enabling allUsers to invoke it.

So, to deploy, we run ./deploy.sh. In the output of the commands, you'll se the URL that GCP assigned to your function.

Go to it using your browser, and you'll be able to see "Hello World" printed in your screen.

Still feel like you missed something? Take a look on the source code for this tutorial: https://github.com/wrongbyte-lab/cf-tutorial

What I learned working for a big company

wrongbyte — Thu, 17 Nov 2022 17:20:39 +0000

There are undoubtedly many paths one can follow in their career as a programmer; and it's not about choosing backend, frontend, or an specific language to work with: it's about one's attitude and choices when it comes to development.
However, often the environment in which you work has a lot of influence on which kind of dev you are going to become, as well as how long it will take for you to advance on your career. One of the decisive factors is the size of the company you work for.

Part 1: How a company shapes developers

As said previously, the environment in which you spend a lot of time has a great influence over you and your work. Some companies place emphasis on skills that other companies undervalue. This dynamic is responsible for shaping devs differently across different environments, and it is something important to understand because the more adaptable you are, the greater the chances to be successful in your career.

1- The generalist vs. the specialist

I'm the kind of developer who likes to know how an application work, end-to-end - from the CSS to the choices for cloud providers. Although it's fun to do so in my personal projects, often it's not something possible to do in a big company.
However, this is not exactly a bad thing. As applications grow in size, it becomes more productive - for the devs and managers - to split responsibilities between scope-specific teams. It keeps them focused on a smaller scope, making it easier for new devs to get the context and quickly start to contribute to the codebase.

It means less space for fullstack, generalist devs and more space for professionals who act on a more specific scope and are used to solve similar problems. In my last job I was the first fullstack on the team, which created some minor friction since this kind of role was something completely new in an environment where people worked in strictly defined scopes.

2- Soft and hard skills

Before my first experience as a developer, I thought hard skills were the decisive factor when it comes to advancing quickly in seniority. Is it true? Well, it depends.
Acting on a smaller scope means having a smaller surface under your/your team's responsibility. In practice, it implies having different services under the responsibility of different people - and since many of these systems are interconnected, the people must be as well.
It creates a contradiction - in theory, splitting responsibilities should increase teams' productivity and reduce coupling. But in practice, this is not always the case, because sometimes solving a cross-platform problem requires talking to a lot of different people. You will have to roll up your sleeves and prepare to make all these people understand your problem and look for a solution together.
Obviously, this will require much more than bare technical skills - it will demand from you a concise and effective communication.

Therefore, the larger the company, the greater the need to evolve your skills beyond code and focus on making your communication effective and positioning yourself proactively. This is the key to being a professional who makes a difference in this kind of extremely interconnected environment.

Sync and async work

Sometimes calls cannot be emails.
And sometimes you'll have to bet on sync communication to make things flow quicker, specially when there's no available documentation on sight.

However, this is precisely the point where many managers fail - identifying when sync communication is really necessary. So, you will have to be prepared for meetings, calls and sometimes unnecessary Scrum ceremonies. The greater the company, the greater the probability of this happening, because management teams tend to be more distanced from developers and thus have a distorted perception of which things are really important.

The lone programmer vs. the System Design Engineer

I had a colleague who used to put a great emphasis on how "developers" are different from "architects/engineers". Although I disagree in parts, there are many contexts in which this analogy is true. Specially in the context of this post - big companies.

Developer	Architect
Knows all language-specific quirks	Language-agnostic
Focus on writing optimized code	Focus on integrating systems
Understand how things work under the hood	Understand how things communicate
Detail-oriented	Big-picture thinker

Can you be both? Yes, you can.
But the environment in which you are usually tends to favor one type over another.
Usually, more "structured" software will imply on less worries about details. This is often the path that corporations follow as they grow - they abstract things over time to gain productivity and reduce the required boilerplate to develop things.
You'll see it in the use of internal libraries or in the adoption of more opinionated frameworks; they reduce the quantity of micro technical decisions and favors the second type over the first one. But they also represent a very important downside of working in a big company: you'll have to take less important decisions.
And it is very good for businesses, but sort of bad for developers, specially if your desire is to learn as much as possible. You'll have less context under your hands and therefore, less opportunities to make mistakes and learn from them.

Finally, it is important to keep in mind that the points listed above are not inflexible rules - rather, they are trends that I have personally been able to notice while working in and getting to know the environment of different companies.
As a developer, the bottom line is to be as adaptable as possible within your context, and especially to have a sense of what to expect beyond the code in each of the companies you set out to work for.

What are closures?

wrongbyte — Thu, 29 Sep 2022 23:57:17 +0000

The concept of closure is important when it comes to understanding how languages such as Javascript work - and how scopes, lifetimes and references come together and can be combined to provide useful features to programmers.

Variables and their scopes

1 - Local and global scope

Every time you use a variable inside a function, this variable needs to be declared somewhere - and this place can be the local scope (inside of the function) or the global scope.
Variables declared in the local scope are only accessible inside of their parent function - which means you cannot reference them outside of the function:

function() {
  let a = 1;
  console.log(a); // works
}    
console.log(a); // fails

In the example above, written in JS, we get an Uncaught ReferenceError: a is not defined.

However, by declaring a as a global variable, we can reference it anywhere in our code:

var a = 1;
function() {
  console.log(a); // works
}    
console.log(a); // works

2 - Lifetime of entities

The behavior above happens because entities (variables, constants, etc) have different lifetimes across a program depending on their scope. The definition of the "lifetime" of an entity can be thought as the period from its creation (allocating memory for it) to its destruction (deallocating the memory used for this variable).

A global variable has the same lifetime of the entire program. Local variables, however, have specific lifetimes, so they may not be "alive" during the entire program’s lifecycle.
Hence, the underlying programming language must provide a way to deal which such cases, such as manual memory management or some kind of garbage collector. Otherwise, one could stumble upon a dangling reference when not careful enough, since deallocated variables cannot be referenced.

This dynamic is important to understand because we'll eventually get into a tricky question:

What would happen if we wanted to reference a variable outside of its original scope?

3 - Nested functions

There is a special use case of functions in which we face the question above.
Let's say we wanted to create a function inside of another function. Let's call them outer and inner.

const outer = function() {
  const inner = function() {
     console.log("hello");
  }
}

Everything declared inside of inner has now access to the scope of outer.
It means that we can declare variables inside of outer and then use them inside of inner, as it follows:

const outer = function() {
  const a = 1;
  const inner = function() {
    console.log(a);
  }
  return inner;
}

var fnc = outer(); // execute outer to get inner 
fnc();

We can then return inner from outer. This part is important because it permits inner to leave the scope of outer.
After that, we assign the return of outer to a variable fnc, which we can execute to get inner.

Therefore, we now have all variables of inner, declared in outer, closed under this function.

What we'll seeing here is basically the implementation of closures in Javascript: a function that has access to the additional data from its surrounding scope.

Therefore, we can define a closure as:

1 - A function and
2 - A reference to that function's outer scope

In the example above, our function is inner and the outer scope is the scope of outer, which has the variable a. Without keeping a reference to this surrounding scope, we would not be able to retrieve the value of a. Once we have a reference to this surrounding scope, we have a closure.

Back to scope and lifetimes: what would happen if we didn't have closures?

There are languages that don't implement closures.
C is a good example: in C, you won't have closures as well as native support for nested functions.
Using the simplified definition we've seen before, we can say that what's needed to implement closures is a record of the function along with its environment.
To do this in C, there would be necessary to use structs, function pointers and a lot of fuzzy code. Furthermore, it would be necessary to have support for nested functions, which C doesn't have by default. Since closures are only meaningful when a function needs to be executed outside of the scope in which it was originally declared, having nested functions is essential for this concept to work.
A lot of work, huh?

How Javascript solves it?

We already learned that JS implements closures and what they are. But how does it work under the hood?

Every function in JavaScript maintains a reference to its outer environment. This reference is used to determine the execution context of the function when it is invoked, and therefore enables the function to "see" variables declared outside of it.
It creates a kind of state particular to the functions declared in the same lexical environment.

💡 The lexical environment consists of any local variables in the function’s scope when the function is created.

In addition, if we have functions that call other functions that in turn call even more functions, JS creates a chain of references to the outer lexical environments - which is called the scope chain. Therefore, closures in Javascript can become quite useful - and we are going to see a few uses for them now.

Why are closures useful?

If you have ever programmed using an object-oriented language, you will probably know the concept of classes and states.
Once you use a closure, you are creating the equivalent of a private state associated with a function.

function foo() {
  const secret = Math.trunc(Math.random() * 100)
  return function inner() {
    console.log(`The secret number is ${secret}.`)
  }
}
const f = foo() // 
f()

In the example above, secret is not directly accessible from outside foo. foo then creates a kind of encapsulation similar to what we see in OOP, which is useful in several cases. Furthermore, JavaScript did not have a class syntax until 2015 - making the use of closures an alternative.

Finally, there are several other use cases for closures - for example in functional programming, event-oriented programming and so on.

💡 Further reading: Nested functions, closures and first-class functions

Cryptography basics: breaking repeated-key XOR ciphertext

wrongbyte — Tue, 05 Jul 2022 22:30:42 +0000

In this post, we are going to learn a bit of what is the XOR encryption algorithm and how to decipher it through Friedman Test using Hamming Distance and Frequency Analysis.

First of all, what exactly is a XOR cipher?

If you ever studied bitwise operators, you have already heard of exclusive or, or simply XOR.
It takes two inputs and returns 1 if these inputs are different.

But the interesting part is that this simple operation, that happens in the bits level, is very useful for composing cryptographic keys. That's what we'll see in this post, using a bit of Python and the problem presented in the 6th challenge of Cryptopals (set 1)

How can we use XOR as a method of encryption? In fact, what is a cryptographic cipher?

To answer this question, let's think in terms of functions. Encrypting a message is taking its plaintext (or, more precisely, its bytes), and generating an appearing random output with the help of an encryption algorithm. This algorithm defines the pattern we'll follow when replacing the original content with the encrypted one.
For example, the Caesar cipher replaces a letter with its corresponding following letter, such that "ABC" becomes "BCD". This pattern goes through the whole message.
But the Caesar cipher can skip more than one letter - what matters here is the logic of substitution. In this way, the XOR cipher is very similar.

Bytes, ASCII and single-byte XOR

Before introducing the encryption with a repeating cipher, let's first understand how a single-byte encryption would be done.
The encryption with a single-byte XOR cipher is made when we use the XOR operation to change the value of each byte; we make this operation in the whole text using a key - that is the constant value which we are going to use to do this operation.



binary_string = b"hello"
for byte in binary_string:
   print(byte ^ 100)

The outputs will be 12, 1, 8, 8 and 11.
It happens because each letter in a binary string can be represented by a binary number that, XORed against 100 (the key here), returns a different byte. This number could be any value within the range [0, 255].
Therefore, here 100 acts as our key - we would need to know this value to perform the decryption of the message. Using a XOR cipher is a symmetric encryption method, what means that we need the same key both to encrypt and decrypt a message. It happens because XOR is an involutory function - it's its own inverse, so to decrypt a message we would need to simply XOR its bytes against the key again.

So, we already have a substitution cipher similar in terms of Caesar cipher, but a bit more sophisticated.

Side note 1: it turns out that not all XORed bytes will be printable, since they can be outside the ASCII range. In this case, we can make a conversion to base64, for example, to print them. See (in Portuguese).
Side note 2: the article above can also be helpful to help you understand how things work with ASCII characters in byte-level.

Repeating XOR cipher

It turns out that encrypting something with a single-byte key would be a very weak encryption method. To break it, we would only need to know which key was used - which could be achieved by bruteforcing all the 256 possible values. Then, we could look at the outputs of these operations and choose the one that is more "English-like", by assign scores to each output, based on the most frequent letters across the English language.

PS: remember this function, we are going to see it later again!



# Breaking a single-byte XOR cipher: we perform a XOR operation
# in the string using all possible values for the key.
# The key used to generate the output closer to English is what we are searching for.
def assign_score(output_string):
    string_score = 0
    freq = [' ', 'e', 't', 'a', 'o', 'i', 'n', 's', 'h', 'r', 'd', 'l', 'u']
    for letter in output_string:
        if letter in freq:
            string_score += 1
    return string_score

def XOR_decode_bytes(encoded_array):
    last_score = 0
    greatest_score = 0
    for n in range(256): # checks for every possible value for XOR key
        xord_str = [byte ^ n for byte in encoded_array]
        xord_ascii = ('').join([chr(b) for b in xord_str])
        last_score = assign_score(xord_ascii)
        if (last_score > greatest_score):
            greatest_score = last_score
            key = n
    return key

So, we can make it harder to break by simply creating a longer key - with more bytes and that repeats itself across the text.
It would require us two steps to break: first, we would need to know the length of the key, and then we would need to know the key itself - which means testing each possible value for each one of the key's characters. A bit more complicated, right?

So, let's understand how to encrypt a text using a XOR repeating key first.

Repeating key: encryption



input_text1 = b"Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal"
XOR_key = b"ICE"

def XOR_repeating_encode(input_string: bytes, key: bytes) -> bytes:
    xord_output = []
    print(input_string)
    for i in range(len(input_string)):
        xord_output.append(input_string[i] ^ key[i % len(key)])

    return bytes(xord_output)

The logic here is pretty the same we used for the single-byte key. In short, we perform a XOR operation against each of the characters of the key, which is ICE here. So, "B" is XORed against "I", "u" against "C" and "r" against "E", and so forth until we reach the end of the text. Getting the plaintext back is achieved through the same process.

But what if we wanted to recover the plaintext without knowing the key?

Here things start to get interesting. Let's see how to break a repeated-key XOR ciphertext!

1 - The key's length: Hamming distance

How far is "a" from "d"?
You may say that they are a few letters apart in the alphabet. But there's another interesting way to measure their "distance": how many different bits they have - which is their Hamming distance.
So, lowercase a is 95 in the ASCII table, and lowercase d is 100. Their binary representations are 1011111 and 1100100. They have 5 different bits, so their hamming distance is 5.
You can measure this distance across phrases, too - the process is the same, you only sum the result from each pair of characters.

What this measure has to do with the repeating XOR cipher?

The average Hamming distance between two bytes picked at random is around 4.0, while that of any two lowercased ASCII alphabet - whose values range from 97 to 122 - is 2.5.
So it means that the hamming distance between the characters of a plaintext will be much lower than that from a bunch of random bytes - and this information is very useful when we get to test the possible outputs for a variety of possible key lengths.

Let's understand it better.



def hamming_distance(string1: bytes, string2: bytes) -> int:
    distance = 0
    for (byte1, byte2) in zip(string1, string2):
        distance += bin(byte1 ^ byte2).count('1')
    return distance

Checking the different bits of two strings is basically the same as performing an XOR operation on them and counting the 1's, so the function above does exactly this.
Alright. We now have a way to score a string to know the distance between its bytes. How can we use it now?

In this challenge, the range of the size of possible keys is within the interval [2, 40]. Therefore, we will have to do the following steps:
1) Divide our text into different chunk sizes, ranging from 2 to 40.
2) On each iteration - for each chunk size chosen - we will check the hamming score between the chunks.
3) The length of chunks with the lower average hamming distance corresponds to the key's length.

This technique works because, once we get the right size for the key, the chunks will be just XORed plaintext. Therefore, their hamming distance will be way lower than if they were random bytes.



def find_key_length():
     # we are searching for the length that produces an output with the lowest hamming score
     min_score = len(text)

     for keysize in range(2, 40):
        chunks = [text[start:start + keysize] for start in range(0, len(text), keysize)]
        subgroup = chunks[:4]
        # getting the average hamming distance per byte
        average_score = (sum(hamming_distance(a, b) for a,b in combinations(subgroup, 2)) / 6) / keysize
        if average_score < min_score:
            min_score = average_score
            key_length = keysize

    return key_length

In the code above, the logic is as it follows:
Let's say that we are guessing that the key is 4 characters long. If we had the following text:



text = "YWJjZGVmZ2hpamtsbW4="

We would divide it in several chunks with four letters each:



chunks = ['YWJj', 'ZGVm', 'Z2hp', 'amts', 'bW4=']

Now, if we take the first four chunks, we are able to measure the average hamming distance between them:



# keysize here is equal to 4 and subgroup is the first four chunks
# dividing the score by 6 gives us the average diff between chunks, dividing it by keysize gives us the average diff between each a, b bytes for chunk1, chunk2
average_score = (sum(hamming_distance(a, b) for a,b in combinations(subgroup, 2)) / 6) / keysize

2 - The key itself

Once we get the key's length, things get easier.
In this particular challenge, it turns out that the key is 29 characters long. Even though we know the length, we still have 29 characters to guess, each one having 256 possibilities.

How to do that? Well, the answer lies on matrices.



def find_key(key_length = find_key_length()): 
    key_blocks = [text[start:start + key_length] for start in range(0, len(text), key_length)]
    # transpose the 2D matrix
    key = []
    single_XOR_blocks = [list(filter(None,i)) for i in zip_longest(*key_blocks)]
    for block in single_XOR_blocks:
        key_n = XOR_decode_bytes(block)
        key.append(key_n)

    ascii_key = ''.join([chr(c) for c in key])
    return ascii_key.encode()

If our key had exactly three characters - say the key was "RED" - then each first character of each chunk would be XORed against "R", the second against "E" and so on.
So, if we joined each nth character of each chunk, the result would be a list of characters encrypted with a single byte XOR cipher, whose key is the nth character of our repeating key!

Oof, that's too much. Let's see it in detail:

The operation of creating an array joining every nth element of each chunk is basically transposing a matrix.
To finally discover the key, then, we just need to apply the function that finds the key for a single-byte XOR ciphertext in each of the lines of our new generated matrix.
And now, we have our deciphered plaintext!

You can see the full code for this post here.

Cracking a hashed password with hashcat

wrongbyte — Thu, 16 Jun 2022 19:16:58 +0000

... through a simple example of how this process works

Given a hashed password $2y$12$Dwt1BZj6pcyc3Dy1FWZ5ieeUznr71EeNkJkUlypTsgbX1H68wsRom, we have only one hint: the password has four letters, all lowercase.

Let's start: finding the hash type

There are a lot of hashes out there. A good way to start guessing is to look at the hashed pass and try to find some kind of pattern. Here, the key is the first 4 characters of the hash.
There is a page where you can look at example hashes: https://hashcat.net/wiki/doku.php?id=example_hashes
Noticed something? We are looking for the bcrypt $2*$, Blowfish (Unix). Our $2y$ matches this pattern. So we are looking for a bcrypt hash. We also can grasp that the hash was generated using a factor of 12 (it is the number that comes after the first four characters).

Let's crack!

First, it is important to know how the process works. Hashing is a process essentially different from encryption - you can only do it once. It means that we cannot really recover the plaintext of a hashed password; instead, we can only compare its hash with our guesses. So, it's like hashing several words and seeing which of them matches exaclty our hash. Then, it must be the password.
We can automatize this process with two tools: hashcat and a dictionary of potential passwords. This kind of dictionary is easy to find on internet, so we are going to use rock you.

Ok, so our dictionary is very large and checking for each password, one by one, would be an expensive operation. But we already know how our password looks like, right? (four letters, all lowercase).
So, let's filter our dictionary a little bit by creating a file containing all the passwords that match our condition:

grep -x -E '[a-z][^0-9]{4}' rockyou.txt > candidates.txt

Here we are using grep along with a regex expression to filter our potential passwords to only four-letters words without digits. The -x flag applies this expression to the whole line (our file contains one password per line), whereas the -E flag is needed because we are using an extended expression (due to the {4} part).

Now, we are ready to crack it with hashcat:

hashcat -a 0 -m 3200 pass.txt candidates.txt --force

Here, the code 3200 stands for the bcrypt hash, and our hashed pass is stored in pass.txt whereas the potential passwords are stored in candidates.txt.

After a few seconds (depending on your computer), we have the result:
$2y$12$Dwt1BZj6pcyc3Dy1FWZ5ieeUznr71EeNkJkUlypTsgbX1H68wsRom:bleh

Where the "bleh" is the password we were looking for.

~~In sum: use a password manager :)~~

How git stores your configs

wrongbyte — Sun, 01 May 2022 19:08:00 +0000

How commits work?

A commit contains information related not only to changes in files, but also to the committers in general. Github, for example, uses emails to link committers to their respective accounts in the platform.

Therefore, working with git configs means directly changing the information associated with your commits.

Viewing your configs

If you have ever had to change or view the name or email displayed in your commits, you probably know the git config user.name command, or its variation git config user.email. These commands are useful to check the information associated with your commits.

But how git stores these configs under the hood?

Local and global configs

Git stores configs in two different ways: globally or locally. Just like npm modules, the difference is where the files will be stored - inside of your current directory or in a system directory, being accessible from your whole system. This differentiation is useful when, for example, working with multiple git accounts on the same computer. You will be able to configure which account you will be using for each repository.

Locally: the `.git` directory

Every time you start a git repository, what you are essentially doing is creating a .git directory inside it. You can open this file in VSCode by navigating to /.git (cd .git) and typing code .
An empty repository will usually have a .git structure like this:

Every interactive git change you do in your repository - that opens a text editor, by default Vim on windows - is going to edit git files in this folder. For example, let's say we forgot to use the -m flag when committing changes and it triggered a text editor to open:

or, in Vim:

In both cases, what you are doing is editing a file called COMMIT_EDITMSG inside of your .git directory.

It also happens when you use the rebase -i command; in this case, you create a directory called rebase-merge, that contains the file git-rebase-todo, which is where you are going to make the changes.
Git is also able to see if there's an ongoing rebase by checking if this directory exists or not:

Okay, but.. What does it have to do with configs?

All of these stuff happens locally, inside of your repository. Naturally, the config file is also there, in a file named config as well.

If you open it, you'll be able to see a file like this:

These settings include the url of the remote repository, and some information about branches and merges.
See, for example, what happens if we change the "origin" - the remote url - to something different, by changing its URL:
git remote set-url origin google.com

Now, our remote URL points to google.com in the current repository.
Commands such as git remote set-url origin are shortcuts for editing the config file directly in your CLI. But these properties are not the only ones you can change; let's say that we have multiple github accounts and want to set which one we are going to use for commits in a particular repository.
We can do so by adding, to our config file, the following properties:

By doing so, we are overriding, for this repository, the global git configs.

Side note: of course, using two github accounts on the same computer requires some additional steps, such as adding credentials to the Windows Credentials Manager, etc. But for customizing the author of commits, the method described here works.

Okay, but.. Where are the global git settings stored?

Even though you want to change the committer's information for a repository, git has some default settings what will be shared with every new file tracked with git in your system. These are the global configs, and you can see them by typing git config --list --global. ~~yeah, it also works with the --local flag~~
Unlike the local configs, the global ones are stored inside of a file called .gitconfig, that is inside of your system user directory. The changes applied to this file will have the same effect of setting things in the git CLI with a --global flag.

In conclusion...

Even though it's not very common to make changes in .git files directly (instead, you are probably going to use git bash), it may be useful to understand a bit of how things work under the hood. After all, git deals with your files by creating also some other files to track information. I encourage you to take a look not only at the config file but also at other files and folders inside .git, you may find interesting things there!

The basic CSS guide for non-frontend developers

wrongbyte — Thu, 24 Mar 2022 00:36:52 +0000

This post is not intended to be a kind of cheat sheet; I'm not going to cover every existing CSS property. My intention here, on the other hand, is to present some useful CSS properties in a holistic way, showing how they can be used together and the logic behind them.

I'm not a front-end developer though, so if something here seems a bit strange or confusing, I encourage you to look up on other resources. I hope this post is useful.

Box-model

This one is the basics that you probably already know.
Every single element in a page is nothing but a box containing these properties you see below:

Although important, I feel that most struggles people have have nothing to do with the box model itself, but with positioning each element in relation to each other. So, I will skip box-model for now; even though we'll see a bit of it later.

Part 1 - Display: inline, block, inline-block

We know that elements are built just like blocks in a page. However, are all elements equal when it comes to displaying them in your document?

The answer is no: they can be displayed occupying all the space around them or inside another block element, depending on the default value of their display property.

Let's see.

Let's say we have a very basic p tag containing some text. To write another paragraph, we would have to add another p tag as follows:

`display: block`

By default, p is an element whose display property is set to block. The meaning of it is exactly what you saw above: block elements occupy all the width where they are positioned. That's why we cannot have two p elements side-by-side, without changing their display property.

`display: inline`

Let's say we've decided that our lorem ipsum text looks boring without some colors. So, we need to change some stuff inside of p, which is a block element. How to do it?

The answer is: display: inline. Therefore, in this case, the best element we could use - that is inline by default - is <span>.

Our HTML now looks like this:

<p>"<span class="highlight">Lorem ipsum dolor sit amet</span>
,consectetur adipiscing elit, sed do [...]</p>

Basic differences between inline and block

The width of your block elements will not adjust to the content inside them; whereas it will happen with inline elements.
In fact, "how to make my div adjust its width to the content inside" is a common question when it comes to CSS, and its answer is often setting the display property to inline-block (which will have characteristics of both inline and block). Look at the answers of this question in Stack Overflow.

Another difference that is worth noting is that block elements have top and bottom margins (remember the box model). That's visible in the image above.

But why do these differences even exist?

A key concept to keep in mind is that block elements are intended to be used as "wrappers" of sections in your page. That's precisely why elements such as <main>, <header>, <article>, <footer>, <div>, etc are block elements by default. They are supposed to have content inside them; therefore they start a new line and take up the full width available. They are just like drawers.

On the other hand, inline elements are like the items inside the drawer. Therefore, they occupy only as much width as necessary and are intended to be used inside block elements. It's easy to position they side-by-side.
Some elements that are inline by default are <a>, <button>, <textarea>, <label>, <select>.

Side note: grid and flex are other important values for display, but we'll skip it for now, because a section of this post we'll be dedicated exclusively to grid and flexbox.

Let's add some colors to these paragraphs, first wrapping them in a div.

HTML

      <div class="wrapper">
          <div class="yellow-div">
            <p>"<span class="highlight">Lorem ipsum dolor sit amet</span>, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."</p>
          </div>

          <div class="blue-div">
            <p>"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."</p>
          </div>

CSS

.yellow-div {
    background-color: yellow
}

.blue-div {
    background-color: blue
}

.wrapper {
    width: 800px
}

Now our paragraphs look like this:

Our div now has a width of 800 pixels. But now we face our first problem: what if the width of our screen is less than 800 pixels?

Part 2 - CSS Units

If we wanted that our div had always half the width of the page, it would be a headache to define its value in pixels. That's what would happen with our example: there are a lot of screens that are less than 800 pixels wide. But pixels are only the tip of the iceberg.

Relative lengths

Pixels and centimeters are pretty self-explanatory. They are absolute, fixed length units and do not change in spite of other characteristics.
However, due to their static nature, when dealing with responsive layouts, they are not always the best option. That's why I will focus here on relative units.

`em`

em is equivalent to the font-size of parent div. It means that, for example, if the font-size of elements inside yellow-div is set to 14px, then inside yellow-div, 1em is equal to 14px, 1.2em is equal to 16.8px and so on.

`rem`

This unit is similar to em, but in this case we take for reference the font size of the root element (often <html>). So, differently from the example above, we would not use the font-size of only yellow-div. If the font-size of the page is 18px, then 1rem would be equal to 18px in all elements of our HTML.

`vh` and `vw`

These are my favorite units for responsive layout. vh stands for viewport height and vw stands for viewport width. They represent either 1% of width or height of page - and they resize accordingly to the viewport size. That's very useful when you want, for example, a div that occupies half the page both in mobile and desktop screens.

So, what about resizing our div to have 50% of the width of our page, despite of the screen size? Let's do it:

.wrapper {
    width: 50vw;
}

Look how the proportion is kept in smaller screens:

Looks nice for now. But it could be better if our div was centered horizontally. How to do it?

Part 3 - centering stuff with CSS; an introduction

We are back to the question that opened this post - how to center a div?

The answer for this question varies a lot, actually. But we are going to start with the basics, first with two questions:

1 - Where is the element that you want to center?

2 - What's the nearest reference you are going to use to center it?

The first question is very important at this point, because out HTML has only a div with two paragraphs inside. It's different from a column in a blog template or some design alike. So, our element is floating alone in a HTML document and we are going to center it relative to our viewport.

This case is not the most common; you are probably going to need to center your elements inside of other elements, and therefore the solution would be different. But for now, let's stick with it.

.wrapper {
    width: 50vw;
    margin: 0 auto;
}

By simply adding margin: 0 auto, we are able to center our div in this case.

It is responsive as well:

Back to box-model: why the solution above works

Defining margin: 0 auto does precisely two things: it sets the element's vertical margins to zero and lets the browser decide the horizontal margins - that will be equal in both sides. Of course, the values for the child element will be calculated relative to its parent element - and as we only have this div, the parent element is <body> and so we are able to center it absolutelly.

However, using margins to center elements only works if:

1 - The element has a defined width

2 - The element is block (because we cannot define width for inline elements)

So, as you see, this approach is useful - but only for very specific cases.

Side note: margin auto only works for centering things horizontally. It does not work on vertical axis the same way, look at the answers of this question.

And so we get to another question: how to center stuff vertically, if we cannot use margin?
There are plenty of answers to this question. And to answer them, it's time to use another CSS property.

Part 4 - `position`

Here things start to get interesting.
In the previous example, let's say that we want to center our div vertically, taking for reference the browser window.

Even though there are other ways to achieve it, we are going to use position here.
Let's start with the most useful cases: absolute and relative.

They set how the element should be positioned relative to:

1 - Its default position in the HTML document - position: relative

2 - Its parent element - position: absolute

When you set position, you can define top, right, bottom and left properties, that will define the element's final position in the page layout.

What's the difference between them?

In simple words, absolute takes for reference the ancestor element and relative takes for reference the default position that the element would occupy in the page, if position is not set (normal flow). Look at the previous image and observe how elements are positioned. Relative will take for reference exactly these positions.

`absolute` is kinda tricky

When we say takes for reference the ancestor element, what exactly it means?

Basically, the reference for a absolute-positioned element is its nearest positioned element, what is, the nearest element whose position is different from static (the default value).

When we don't have this positioned element, though, the reference used will be the root element (<html>). Let's see it in practice:

Questionably centering with position

So, we want our div to be centered vertically in terms of the browser window. If we use the root element for reference, absolute would be the right choice, right? To test it, we are going to use the same logic of applying 50vh.

.wrapper {
    width: 50vw;
    margin: 0 auto;
    position: absolute;
    bottom: 50vh;
}

But look what happens:

Now our layout is broken because our element's margins are being ignored.

In fact, that's precisely what is intended to happen. When you use the absolute positioning, your element is removed from the document flow, what means that its box is ignored.

The margins are still there, but they have no effect now that our element is not part of the layout anymore.

But we still want our div to be part of the layout. So, let's use position: relative instead.

To do so, we can't use 50vh as our distance from the bottom, because now our reference is not the distance from the bottom of browser window anymore, but the default position of the element. So, setting bottom: 50vh with position relative would make our element disappear from the page.

Then, we can use the distance from top to do it. However, this distance certainly is not 50vh anymore.
Why? Because it's not 50vh from top of page, but 50vh from where the element should normally be.

A way around this problem is to define the position value to 50vh - half the height. If the div has a height of 200px, our CSS now looks like:

.wrapper {
    height: 200px;
    width: 50vw;
    margin: 0 auto;
    position: relative;
    top: calc(50vh - 100px);
}

And our div is now vertically centered.

An important property: `absolute` inside `relative`

It would be nice if we could position one element in terms of its parent div just like the drawer analogy, right? In fact, this is possible combining absolute and relative elements.

It happens exactly because absolute (the yellow div, in this case) takes for reference the closest positioned element. And this element, here, is our wrapper div.

Look how we can define the properties above:

.yellow-div {
    position: absolute;
    right: 0;
    height: 100px;
    width: 100px;
    background-color: yellow
}

Now, right: 0 positions the yellow-div in terms of its parent div.

Important: there are other values for position. I will not cover them here, but I encourage you to research a bit about them.

Part 5 - back to `display`: flexbox and grid

The first part of this post introduced inline and block.

Now, it's time to see the pinnacle of layout: flexbox and grid.

Flex and grid are display values that, when applied to an element, allow you to organize the elements inside it as you want. You can organize them in rows, columns, or in personalized areas.

A little disclaimer: I will not describe their utilities in detail because it's probably out of the scope of this post; but I will list the recommended resources to learn each one.

Differences between them

In most cases, their usage overlap and choosing between one or another is more of a personal choice.

But observe the two layouts below:

`grid` - take a brick and divide it

In the first layout, we have the content splitted in several sections. One example of it would be a blog page, where each section have a purpose - one of them may wrap the blog posts, another may show the recent posts, author information and so on.

With grid, you can easily define what's called grid areas. It makes grid very powerful when you want to divide your content in independent, heterogeneous elements. I like to think as grid being a way to divide your content in blocks and straightforwardly personalize their structure. Simply put, it's a method to draw a block and divide it in any way you want, by cutting it into lines.

To learn it in practice, play all the phases of this game and try to create/replicate a layout of your choice using what you understood.

`flex`- organize your items like on a shelf

The second layout presents more homogeneous elements.

The logic of flexbox is a bit different from grid: you can imagine the wrapper div with display: flex being a shelf whose children elements are the items on it.

For this reason, flex is a good choice when you want to organize similar items - like the buttons in a navbar, the images of a gallery, homogeneous content in general. Some properties of flex allow you to choose the order in which the items appear and if they are displayed in rows on in columns. flex also presents the easiest way to center vertically and horizontally the contents of a div:

.random-div {
    display: flex;
    justify-content: center;
    align-items: center;
}

To learn it, the strategy is the same as with grid, play this game instead and try to create/replicate a layout of your choice using what you understood.

After all, how to master CSS?

Personally, I believe that the only answer to this question is to create different front-end projects and practice. Nowadays, it's rare to use pure CSS as you have bootstrap, tailwind and many other frameworks - for example, I used tailwind for my blog!
But using frameworks does not mean that knowing pure CSS is useless. After all, to decide which class to apply to an element, you first have to understand the document flow and what exactly you intend to do.

Frameworks are just a way to prevent you from reinventing the wheel every single day, but they don't write the entire layout for you - you'll eventually need to fix the wheel when it breaks anyway.

Como funciona a codificação em base64?

wrongbyte — Wed, 23 Feb 2022 18:47:14 +0000

Quando falamos de texto - ou, mais precisamente, as letras que compõem o alfabeto - estamos falando de caracteres individuais que são representados da mesma forma que números, quando lidos pelo computador. Isto é, tanto letras e números são convertidos para valores binários.

Veja a tabela abaixo:

Cada letra possui um índice na chamada tabela ASCII. Isso significa que podemos representar letras através de números.
Logo, a palavra "Man" seria representada pelos valores 77, 97 e 110.
Esses valores, por sua vez, convertidos para base binária, correspondem a 01001101 01100001 01101110.
Até aqui, nenhuma informação muito nova.

Contudo, o que acontece se quisermos codificar dados binários e transmiti-los através de locais que são designados para lidar com dados em texto (caracteres alfanuméricos)?
A forma escolhida para fazer isso de maneira otimizada é codificar os dados na base64.

O que é base64?

Imagine que você quer inserir uma imagem em uma página web. Temos então um típico caso no qual a conversão para base64 é útil: páginas HTML são otimizadas para texto, e portanto converter as informações binárias para texto se torna interessante.

Como funciona a codificação?

Para simplificar, vamos utilizar o exemplo anterior.
A palavra "Man" é representada por 3 bytes, 01001101 01100001 01101110.
Cada byte possui 8 bits, porém para iniciar a codificação para base64, precisamos que cada caractere corresponda a 6 bits. (Detalhe: 2^6 é igual a 64, o número total de valores possíveis em base64, portanto o nome da codificação)
Isso é feito juntando os 3 números, obtendo uma string de 24 bits: 010011010110000101101110.
Dividindo a string de 24 bits em 4 dígitos de 6 bits cada, temos agora:
010011 010110 000101 101110, que correspondem, em decimal, a 19,22,5 e 46.

O próximo passo é encontrar a correspondência de cada dígito na tabela base64:

Finalmente, isso nos dá TWFu como resultado. A codificação está feita. 🎉

A divisão em 24 bits e padding

Sabendo que a conversão para base64 se dá em grupos de 24 bits, ou de 4 dígitos com 6 bits, chegamos a uma questão importante: o que ocorre caso não tenhamos os 4 dígitos completos?
Vamos supor que em vez de "Man", tenhamos "Ma". Isso resultaria em dois bytes, ou 16 bits no total.
O próximo múltiplo de 6 é 18, logo, para que possamos ter 3 dígitos de 6 bits, precisamos adicionar 2 bits na string representada.
Isso significa que 0100110101100001 se torna 010011010110000100, porque adicionamos 2 bits - dois zeros - no final, o que é chamado de padding. Assim, podemos então dividir essa string em 3 dígitos de 6 bits e adicionar um quarto bit para completar o quarteto. Esse bit é o padding que, na hora da conversão para ASCII, vai ser representado por =. Então Ma corresponde agora a TWE=.
Veja, no exemplo abaixo, alguns casos onde o padding é adicionado:

É importante notar que nem sempre o padding vai ser obrigatório, já que é possível saber se há bits que faltam pelo tamanho da string codificada - já que esse número deve ser sempre múltiplo de 4.