DEV Community: Gregory Gaines

Emulating PS2 Floating-Point Numbers: IEEE 754 Differences (Part 1)

Gregory Gaines — Tue, 21 Nov 2023 22:56:18 +0000

Terminology

Term	Description
IEEE 754	A technical standard for floating-point numbers established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). Most modern computer hardware follows this standard.
SoftFloat	A software implementation of floating-point arithmetic.
PS2	Shorted name for the PlayStation 2 console.

Introduction

This is the start of a series about emulating PS2 floating-point numbers. Emulating PS2 floating-point numbers is a bit of a pain because it does not follow the IEEE 754 standard like most modern computers. The PS2 uses its own variation of the IEEE 754 standard I like to call either the PS2 IEEE 754 variant, PS2 floating-point variant, or PS2 float.

Floating-point operations are usually preformed by the hardware of the host machine which usually follows the IEEE 754 standard. That means your phone, pc, or your Mom's old laptop all most likely follow the IEEE 754 standard.

Unfortunately, due to the PS2's IEEE 754 standard deviation,
we can't use the standard floating-point operations when programming. Instead, we have to design a custom implementation to emulate PS2 floating-point operations by software. This is called a "SoftFloat" or "Software Floating-Point".

Problems With Emulating Floating-Point

SoftFloat implementation most of the time are MASSIVELY slower than hardware no matter how its designed. Instead of a computer chip directly computing the floating-point, we have to programatically calculate and call functions to get the same results.

Then we have the issue of debugging. Our soft-float implementation is not compliant with the IEEE 754 standard and we have to use the PS2 as a baseline to verify results. If we have an issue, we have to investigate whether its a bug or an undocumented quirk in the PS2 IEEE 754 variant.

Floating-Point Format

I will quickly explain the floating-point number format; be wary that some details will be missing. If you want to learn more about floating-point numbers, I recommend checking out the IEEE 754 Wikipedia,
References, or searching the web.

A 32-bit register stores a floating-point number with the following structure

32-bit floating-point number

Bits 22-0 are called the fraction bits, mantissa, or significand. I will be using the term mantissa.

  Name       Bits
  ------     ------
  Sign       31
  Exponent   30-23
  Mantissa   22-0

The Sign Bit

Bit 31 is the sign bit. A 0 denotes a positive number, and a 1 represents a negative number. Flipping this value flips the sign.

The Exponent

The exponent field is between bits [30-23] and needs to represent both positive and negative exponents. Because the field is an unsigned integer (always positive), the value stored in the exponent field is offset from the actual value by an exponent bias.
To get the actual exponent value, subtract the exponent bias from the value stored in the exponent field. For IEEE 754 single-precision floats, this value is 127, that means the exponent field can represent values from -127 to 128.

Exponent Field Value	Actual Exponent Value
0	-127
127	0
200	73

For example, to express an exponent of zero, store 127 in the exponent field. Similarly, an exponent value of 200 resolves to 73 or 200 - 127 = 73.

The field is a base 2 number but not stored in base 2 form. When converting a floating-point decimal into a float, the exponent is expressed in base 2 form using 2^(exponent - 127).

The Mantissa

Bits [22-0] make up the mantissa or fraction, which is the precision of the number to the right of the decimal points.
Even though the mantissa is 23 bits long, there is a leading hidden bit called the "implicit leading bit" (left of the decimal point) which is not stored in the floating-point number which actually makes it 24 bits long. When the mantissa is extracted and used for arithmetic, you add the implicit bit by setting bit 23 of the standalone mantissa.

When the mantissa is stored back into the floating-point number, you remove bit 23 to delete the implicit bit. The implicit bit is always assumed to be 1. If you read IEEE 754 docs and see the mantissa referred to as 1.mantissa, the 1. is the implicit bit.

Floating-point numbers are typically normalized,
meaning there is a non-zero bit to the left of the radix point (decimal point) or the mantissa is zero. Technically speaking, when we perform arithmetic operations on the mantissa and the mantissa is greater than zero, the first set bit if the mantissa MUST BE BIT 23 (the implicit leading bit).

If the exponent field is greater than zero, the implicit leading bit is assumed to be 1. This means that the mantissa is actually 24 bits with an invisible leading bit of 1, and space is saved by not storing it.

If the exponent field is zero, then the implicit leading bit is assumed to be 0 as well. This is called a denormalized number.

The PS2 doesn't support denormalized numbers and during arithmetic operations, truncates any denormalized numbers to zero.

Putting It All Together

In summary:

The sign bit is 0 for positive numbers and 1 for negative numbers.
The exponent field contains 127 plus the real exponent for single-precision.
The exponent field is base 2.
The first bit of the mantissa is typically assumed to be 1 and represented in docs as 1.mantissa.

Representing in Code

Floating-point numbers as a struct:

struct Float {
  sign: bool,
  exponent: u8,
  mantissa: u32,
}

Converting into a decimal:

impl Float {
  /// Convert the struct into a decimal
  fn to_decimal(&self) -> u32 {
    let mut result = 0u32;
    result |= (self.sign as u32) << 31;
    result |= (self.exponent as u32) << 23;
    result |= self.mantissa;
    result
  }
}

Converting Into a Float

Since PS2 floats don't follow the IEEE 754 standard, we will represent them as structs or in decimal form. Once in decimal form, its useful to convert the decimal into a regular 64-bit float data type or f64 to see its string representation. Even though a PS2 float is 32 bits, we don't use f32 because there are cases where a PS2 float in decimal form would result in "NaN" (not a number), "Inf" (infinity), or a bigger number that whats allowed in the IEEE 754 standard.

A 64-bit float or f64 is the only type that can represent these values since it has a larger range than f32 as it follows the IEEE 754-1985 which allows a bigger range of numbers that luckily covers abnormal PS2 float cases.

Here is the algorithm for converting a decimal into a float:

num = (si ? -1 : 1) * 2 ^ (exponent - 127) * (1.mantissa)

float num = (sign ? -1 : 1) * Math.pow(2, exponent - 127) * (mantissa / Math.pow(2, 23) + 1)

expanded:

/// Convert a decimal into a floating-point number using the IEEE 754 standard.
fn as_f64(f: Float) -> f64 {
  // Get real exponent value by subtracting bias
  let mut exponent = f.exponent - 127;

  // Raise exponent by the power of 2
  exponent = 2.powf(exponent);

  // Get mantissa and put it behind the decimal point
  let mut mantisa = f.mantissa / 2.powf(23);

  // Add implicit leading bit
  mantisa = mantisa + 1;

  // Multiply mantissa by exponent
  let mut result = mantisa * exponent;

  // If sign bit is set, make result negative
  if f.sign {
     result = result * -1;
  }

  return result;
}


fn main() {
  // 3.75
  let float_struct = Float {
    sign: false,
    exponent: 0x80,
    mantissa: 0x700000,
  };

  // 3.75000000000000000000000000000000
  println!("Float representation: {:.32}", float_struct.as_f64());

  // 4.3
  let float_struct_2 = Float::new(0x4089999A);

  // 4.30000000000000000000000000000000
  println!("Float representation: {:.32}", float_struct_2.as_f64());
}

Differences from IEEE 754 Standard

NaN Does Not Exist

In the IEEE 754 standard,
NaNs represent undefined or unrepresentable values,
such as the result of a zero divided by zero.
A NaN is encoded by filling the exponent field with ones,
and some non-zero value in the mantissa.
This allows the definition of multiple
NaN values, depending on what is stored in the mantissa field.

An example of NaN encoding:

|31|30---------23|22-------------------------------------------0|
|s |  11111111   |       xxx xxxx xxxx xxxx xxxx xxxx           |
-----------------------------------------------------------------

The sign bit is ignored, the exponent field is filled with ones, and the mantissa can be anything except zero
because a mantissa of zero would represent infinity.

When NaN are encountered on the PS2, they are treated as normal values, which means the PS2 can represent values greater
than what the IEEE 754 standard allows.

If the mantissa of a NaN is filled with all one's, the PS2 treats these NaNs as
either the maximum possible value Fmax / MAX or the minimum possible value -Fmax / -MAX
depending on the sign bit.

Fmax / MAX or 0x7FFFFFFF:

|31|30---------23|22-------------------------------------------0|
| 0|  11111111   |       111 1111 1111 1111 1111 1111           |
-----------------------------------------------------------------

-Fmax / -MAX or 0xFFFFFFFF:

|31|30---------23|22-------------------------------------------0|
| 1|  11111111   |       111 1111 1111 1111 1111 1111           |
-----------------------------------------------------------------

When a PS2 float with the above NaN encoding is converted into a 32-bit float, we will get "NaN". This is one of the limitations we talk about avoiding in Converting Into a Float when we want to print what the PS2 floating-point number represents. Luckily, a 64-bit float allows for a greater range which allows us to print what the PS2 floating-point number represents.

Infinity Does Not Exist

In the IEEE 754 standard, infinity represents values that are too large or small to be represented.
This is done by setting all the exponent bits to 1 and setting the mantissa to 0.
The sign bit can be either 0 or 1, with 0 representing positive infinity, and 1 representing negative infinity.

Positive infinity encoding:

|31|30---------23|22-------------------------------------------0|
| 0|  11111111   |       000 0000 0000 0000 0000 0000           |
-----------------------------------------------------------------

Negative infinity encoding:

|31|30---------23|22-------------------------------------------0|
| 1|  11111111   |       000 0000 0000 0000 0000 0000           |
-----------------------------------------------------------------

When infinity is encountered on the PS2,
they are treated as normal values, which means the PS2 can represent values greater
than what the IEEE 754 standard allows.

If we tried to convert a PS2 float with the above NaN encoding into a 32-bit float, we will get "+Inf" or "-Inf". This is one of the limitations talk about avoiding in Converting Into a Float when we want to debug what the PS2 floating-point number represents. Luckily, a 64-bit float allows for a greater range which allows us to print what the PS2 floating-point number represents.

Denormalized Numbers Do Not Exist

Numbers with the exponent field set to 0 are denormalized numbers regardless of the sign or mantissa.

Denormalized number encoding:

|31|30---------23|22-------------------------------------------0|
|s |  00000000   |       xxx xxxx xxxx xxxx xxxx xxxx           |
-----------------------------------------------------------------

Denormalized numbers do not exist on the PS2 and during arithmetic operations, the PS2 truncates denormalized numbers to zero.

Rounding Mode Is Always Rounding to Zero

The IEEE 754 standard supports multiple rounding modes:
"Rounding to Nearest", "Round to Zero", and "Round to Infinity".
The PS2 only supports "Rounding to Zero". Also, since "Rounding to Zero" does not require full value before rounding,
unlike the IEEE 754 standard, the results may differ from the IEEE 754 "Rounding to zero". This difference is usually
restricted to the least significant bit only but the details of this are not entirely known.

Floating-point operations need to be rounded because the concept of floating-point is trying to represent infinite numbers with a finite amount of memory.
When performing arithmetic operations on floating-point numbers, the result is rounded to fit into its finite representation. This can introduce rounding errors and is a limitation of floating-point numbers.

Some rounding-errors examples in standard IEEE 754:

0.1 + 0.2 == 0.30000000000000004

4.9 - 4.845 == 0.055 == false

4.9 - 4.845 == 0.055000000000000604 == true

0.1 + 0.2 + 0.3 == 0.6 == false

0.1 + 0.2 == 0.60000002384185791015625000000000 == true

"Rounding to Zero" or truncate means discard the mantissa and keep what's to the left of the decimal point.

Examples but with rounded to zero applied:

round_to_zero(0.1 + 0.2) == 0

round_to_zero(4.9 - 4.845) == 0

round_to_zero(4.9 - 2.7) == 2.0

round_to_zero(9.4 - 3.2) == 6.0

Final Thoughts

PS2 floating-point implementation deviates from the official IEEE 754 specifications.
One solution is emulating floating-point operations using software which is super slow.
PS2 floating-point implementation lack NaN, Infinity, and demoralized numbers.
PS2 floats always round to zero.

In the next article we will learn how to preform arithmetic using PS2 floats in part 2, here is my W.I.P code of my research.

About the Author 👨🏾‍💻

I'm Gregory Gaines, a simple software engineer at Google that writes whatever's on his mind. If you want more content, follow me on Twitter at @GregoryAGaines.

If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

References

A Letter to Rust Users: Don’t Test Implementation Details (Unit vs. Integration Tests)

Gregory Gaines — Wed, 22 Mar 2023 16:54:17 +0000

Howdy Reader

Terminology

Rust Unit and Integration Tests Definition
Why You Shouldn't Test Implementation Details
Bonus Content
Final Thoughts
About the Author

Howdy Reader 👋🏽

A short introduction, I'm a software engineer that's worked on huge enterprise systems at [REDACTED], and a rule I've always followed is when unit testing, "Don't test implementation details". If you have to, you've designed your code wrong. Let's go over how Rust defines unit and integration tests because it differs from the traditional definitions.

Terminology

In Rust, there are no classes, only structs, but I will be using them interchangeably and writing pseudo code for easier consumption for readers.

Rust Unit and Integration Tests Definition 🛠️

Traditionally, a unit test means testing a unit of code like a class, and an integration test focuses on testing between layers like verifying an API call writes the correct data to a database.

In Rust, a unit test is described as a test of the "internal details" of a class like its private functions with access to its private variables because you write the tests inside the class itself, so it has access to the internals.

For integration tests, Rust defines it as a test that can only call the public API aka public functions of a class since you write them outside of the class you are testing. Pretty much how unit testing is for any other language outside of Rust.

Keep these definitions for Rust in mind, I don't want to see any comments with this confusion or I'm shaming you publicly. As programmers, we should not be testing the internal details of a class.

Why You Shouldn't Test Implementation Details 🚫

Rust unit tests allow developers to test the internal details of their classes. When writing tests you should focus on testing behavior NOT implementation. We only care about the results not how we got there.

Here's an example, it's exaggerated of course.

CalculatorV1.rs

// Adding using bitwise and a bunch of private implementation functions
public func add(a: int, b: int) -> int {
  while (isNotEqualToZero(b)) {
    carry = calculateCarryVal(a, b);
    a = calculateSum(a, b);
    b = getCarryVal(carry);
  }

  return a;
}

private func isNotEqualToZero(num: int) -> bool {
  return num != 0;
}

private func calculateCarryVal(a: int, b: int) -> int {
  return a & b;
}

private func calculateSum(a: int, b: int) -> int {
  return a ^ b;
}

private func getCarryVal(carry: int) -> int {
  return carry << 1;
}

Above we calculate the addition of two numbers, in Rust, we can write unit tests for the internal private functions since the tests sit next to the code.

CalculatorV1.rs

// Public Api
public func add(a: int, b: int) -> int {
...

// Private implementation functions
...
private func getCarryVal(carry: int) -> int {
  return carry << 1;
}
...

// Unit tests sitting next to code and testing implementation details.
#[test]
public func test_getCarryVal() {
 int carry = 4;
 assert(getCarryVal(4), 1);
}

#[test]
public func test_calculateSum() {
 int a = 1;
 int b = 2;
 assert(calculateSum(a, b), 2);
}

For an integration test, we only care about the behavior of the public API, so import the public function and test it.

Calculator_Test.rs

...
import add;

#[test]
public func test_add() {
 int a = 6;
 int b = 10;
 assert(add(a, b), 16);
}

This is easy and verifies the expected behavior of the class. Let's say down the road we want to change the implementation details of our calculator to a new implementation called CalculatorV2.

CalculatorV2.rs

// Adding using loop
public func add(a: int, b: int) -> int {
  int result = b;
  while (isGreaterThanZero(a)) {
   result++;
   a--;
  }
  return result;
}

private func isGreaterThanZero(num: int) -> bool {
  return num > 0;
}

After the update, all the internal "unit tests" you wrote are now obsolete and must be removed. Now you have to write new ones:

CalculatorV2.rs

...
private func isGreaterThanZero(num: int) -> bool {
...

// New unit test for implementation details
#[test]
public func test_isGreaterThanZero() {
 int a = 3;
 assert(isGreaterThanZero(a), true);
}

This is one reason why you shouldn't test implementation details. They are flaky and potentially updated for every class change. They aren't very reliable because you are testing them against parameters outside of your public API, and you may be exposing them to conditions it shouldn't operate against which leads to writing unnecessary code instead of focusing on conditions from the public API.

For our integration tests, we don't have to touch anything because we are testing the expected behavior only.

Calculator_Test.rs

import add;

...
// No need to change anything
#[test]
public func test_add() {
 int a = 6;
 int b = 10;
 assert(add(a, b), 16);
}

As for those who think you should test implementation details, take our CalculatorV1. What if another engineer refactored it without any private functions?

CalculatorV1.rs

// Adding using bitwise without private functions
public func add(a: int, b: int) -> int {
  while (b != 0) {
    carry = a & b; 
    a = a ^ b;
    b = carry << 1;
  }

  return a;
}

In this example, we have no internal private functions to test. This is why you shouldn't care about internal details. We can refactor our code to remove all private functions, rewrite them, or combine them all into one function. One thing stays the same, we still have the public API with an expected behavior no matter how the function is implemented.

Do you see why testing internal details is bad? We shouldn't care about any of that, only the behavior of the public API which is the most important should be our main priority, not thinking of all the ways we can break an internal private function that can be refactored or removed the next day.

If your internal functions are so complex that they need tests, then again, your code needs to be refactored or you need to abstract functionality.

Bonus Content 💰

I already see these questions being asked in the comments so I'll answer them here. If you do, I'll shame you publicly.

What about Mocks?
No mocks are not testing implementation details. The boundary between your code and external dependencies is not implementation details.
What about Stubs?
Again, not testing implementation details for the reason above. They can also be used for avoiding introducing complexity into tests.

Final Thoughts 💭

You should be testing the behavior of your class, not the internal details. Tests that focus on internal details are flaky and unreliable compared to tests that focus on testing behavior. Rust even acknowledges the debate of testing internal details, but exposes the functionality anyway. At the end of the day, the public API that exposes a behavior matters the most and that's what should be tested.

About the Author 👨🏾‍💻

I'm Gregory Gaines, a simple software engineer at [REDACTED] that writes whatever's on his mind. If you want more content, follow me on Twitter at @GregoryAGaines.

If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

My Attempt at Running a Gameboy Emulator in Google Sheets

Gregory Gaines — Mon, 26 Sep 2022 07:44:03 +0000

Howdy Reader
Demo
What is an emulator
Shallow Dive into the Gameboy

The CPU
Keeping Components in Sync

Enter Google Sheets
The First Road Block
Creating the Sidebar
Integrating the Gameboy
Final Thoughts
About the Author

Demo
Source

Howdy Reader 👋🏽

You must be thinking "only an idiot would try to run a Gameboy emulator in Google Sheets"? And you'd be right! My favorite programming projects have always been emulators. I was on Google Sheets one day and thought this is boring, and you know what's not boring? Gameboys! It shouldn't be too hard, after all, I've already written one in Java.

We are gonna go over what an emulator is, the basics of the Gameboy, and then the steps to running it in Google Sheets. Let's dive in.

Demo 🎮

Click here for the sheet. Be sure to make a copy or else your sheet won't render. You can do this by clicking "File" then "Make a copy". After copying, you will have to wait a couple seconds for the script to activate which will reveal a new tab in the toolbar named "Gameboy Emulator". Click on the "Gameboy Emulator" tab then click "Show dialog". The script should automatically switch to the "GameboyScreen" sheet, if not switch to it manually.

You may be greeted with an error about not being safe or needing permission. Click yes / proceed on both. And if you are not sure, here is the source.

You can view the code by clicking "Extensions" in the toolbar and click "Apps Script".

What is an emulator 🕹️

An emulator can be summed up as hardware or software that allows a computer system (aka your laptop) to run software meant for another computer system (aka Gameboy ROMs).

A general rule of thumb is the computer system that's emulating another computer system needs to be at-least 3-4x more powerful than the original because of the extra layer's introduced through emulation.

That's how you're able to download Gameboy / PSX ROMs and run them on phones/computers or any device that can download the appropriate emulator.

Shallow Dive into the Gameboy 🥽

The Gameboy is a relatively simple system running a modified 8-bit Z80 Cpu and 64 KB of addressable memory. It also has multiple accompanying sub-components:

LCD
Timers
APU
Serial Port
Gamepad Buttons

When a computer system starts up it runs on a finite loop called the fetch-decode-execute loop.

The CPU

The CPU functions as the brain on a computer and orchestrates the fetch, decode, and execute cycle. It contains 8, 8-bit registers A, B, C, D, E, F, H, and L and can combine them to make 4, 16-bit registers AF, BC, DE, and HL along with the other 16-bit registers SP and PC. Let's see how the cycle looks inside the CPU.

const runCycle = () => {
  // Fetch
  const opcode = memory.read8(pc++);
  // Decode
  const instruction = decode(opcode);
  // Execute
  const elapsedCycles = instruction();

  return elapsedCycles;
}

Keeping Components in Sync

After executing an instruction, a certain amount of CPU cycles have elapsed and we have to keep the entire system in sync. We do this by extracting each component into a class and expose a update function that progresses the component based on how many cycles have passed.

let currCycles = 0;

const runFrame = () => {
  while (currCycles < CYCLES_PER_FRAME) {
    const elapsedCycles = cpu.runCycle();
    lcd.update(elapsedCycles);
    apu.update(elapsedCycles);
    timers.update(elapsedCycles);
  }
}

Enter Google Sheets 📊

That's all I'm going to say for the Gameboy. If you want to know more, read here. Knowing how to start, the next step was writing the code for Google Sheets. Google Sheets runs code using Apps Script which is Google's custom server-side JavaScript runtime made for their web apps.

Diving into the docs nothing seem too different from regular JavaScript so I started writing! The plan was simple. Write the emulator using Apps Script, then display the frames on the sheet.

Simple enough, so I started writing the code and performed simple operations.

// Get sheet meta
const sheet = SpreadsheetApp.getActiveSheet();
const maxCols = sheet.getMaxColumns();
const maxRows = sheet.getMaxRows();

// Resize grid to gameboy dims
resizeSheetToGameboyDims(sheet, maxRows, maxCols);

// Set the size of rows and cols to a gameboy pixel
setSheetRowAndColsToSizeOfPixel(sheet, maxRows, maxCols);

// Clear sheet
clearSheet(sheet);

// Start emulator
startEmulator();

The First Road Block

After a while, my code would automatically fail with no warning. That's when I noticed a major flaw in my plan.

Google only allows 30 seconds of runtime for custom scripts! That means my emulator couldn't run long enough to be useful or debuggable! All was lost until I realized you can create sidebars with JavaScript and HTML.

The plan shifted from running the emulator on the server to creating a client-side sidebar that will contain the context of our emulator and send a draw command to the server to draw the current frame on the sheet.

Creating the Sidebar

An interesting feature of Apps Scripts HTML is that it cannot import JavaScript files, everything must be a .html file. The workaround is to wrap all client-side JavaScript within an HTML file in a <script> tag.

HTML files can be linked using an import function inside <?!= ?> scriptlets which allows you to execute code within HTML. Inside, we run the client-side Apps Script function to load HTML from another file.

<!-- Outputs the Gameboy file inside the current html file -->
<?!= HtmlService.createHtmlOutputFromFile('gameboy.html')
    .getContent(); ?>

Integrating the Gameboy

After some writing, I realized I'm not that good at writing JavaScript so I opted to modify an existing Gameboy core.

Since the emulation logic is already there, all that needs to be done is modify the core's drawing function to send the frame data to the server and draw it to the sheet.

I started by defining logic to draw a 2d array of image data to the sheet.

const drawGrid = (colors) => {
  try {
    const ss = SpreadsheetApp.getActiveSpreadsheet();
    const sheet = ss.getSheets()[1];
    const range = sheet.getRange("1:144");
    range.setBackgrounds(colors);
    SpreadsheetApp.flush();
  } catch (e) {
    Logger.log(e);
  }
}

Now the emulator on the client calls the draw function using the google.script.run.[SERVER_FUNCTION_NAME] function.

google.script.run.drawGrid(frame);

After connecting the functions we got a Gameboy emulator that draws to Google sheets!

Limitations 🚫

It's Super Slow

Turns out the Apps Script API is not that fast. The server commands are slow and drawing is slower. Maybe one of you could experiment and find a speedup solution.

No way to queue commands

Draw commands sent to the server are drawn out of order so you keep seeing frames that were executed in the past. To mitigate, the client queues draw commands and sends the next one only when the previous command finishes.

Final Thoughts 💭

This was an interesting yet disappointing journey. I wish that the Google Sheets API had higher script limits. I did enjoy revisiting the Gameboy and learning about Apps Script even though it's limited.

Even though I didn't get the exact effect I wanted, I got it to draw so I guess that counts as something. Next time, I'll drop a banger project for sure!

Demo
Source

About the Author 👨🏾‍💻

I'm Gregory Gaines, a simple software engineer @Google who's trying to write good articles. If you want more content, follow me on Twitter at @GregoryAGaines.

Now go create something great! If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

DEV Should Remove the Authors Ability to Hide Comments

Gregory Gaines — Fri, 23 Sep 2022 16:41:56 +0000

Intro 📽️

Before jumping the gun, hear me out!

Recently, I wrote the post:

Stop Using .env Files Now!

Gregory Gaines ・ Sep 19 ・ 4 min read

#javascript #webdev #node #productivity

You should check it out, it's a banger!!

Which has more comments than the most liked post on DEV!

And I mean actual comments, not the ones where people repeatedly post the same phrases like "Good job", "Nice!", or "Great Article" over and over.

The Battle Of Comments ⚔️

The comments were a battleground. Wars were fought, insults where thrown, mommas were brought up, and the streets ran red with blood.

The article benefited from the constructive conversations. Even if you don't agree, your side deserves to be heard regardless of whether you are right or wrong. I felt a conversation around .env files needed to happen and it sure did.

That's not to say every comment was positive, when your way of life and intelligence gets challenged, things can get heated.

Here are some highlights of the battle:

A taste of the Battle 🛡️

Someone enjoyed the comments more than the article, should I be flattered?

Another comments enjoyer

Some commenters got snarky

Happened again

I wonder what was said to make them type this?

Someone didn't want to enter the battlegrounds

They must have really been wrong

Well change takes time

I really want to know the context of this

Yikes

I agree 🔥🔥

Why the hide feature should be removed 🚫

Before I stake my claim, here's Dev's official reasoning for introducing the feature.

What about credibility?

I respectfully disagree with everything said. Giving the author the ability to silence criticizers hurts credibility. How do I know I'm reading something right if the author can just delete any comment they dislike? That's why I immediately click off any article that has this at the bottom.

Comments can get heated but sometimes have constructive and intricate arguments attached. People disagree but that's how progress is made.

Not one time did I think "these comments should be removed because I don't like them". Instead, I address and rebuttal comments and this has led to educating others and forming friendships. This is way better than unnecessary censorship.

Author-controlled censorship is a problem. You are giving the author the ability to artificially promote their narrative. What if they post about a very bad practice? They can shut down anyone who disagrees with them.

What about some PR representative posting their buggy or insecure product? Doesn't matter they can remove all comments calling them out.

Do you see how this is harmful?

Lastly, I'm a bit confused about the point of removing comments that corrects the author's mistakes like inaccurate statements or typos.

How is it ok for a commenter to alert the author about a mistake, then the author correcting it and deleting the commenter? How is that helpful outside of protecting the ego of an author who doesn't want to be wrong?

Final Thoughts 💭

I just don't see the need for an author to remove comments. I feel unnecessary censorship hurts the community as a whole. Anyone can force a narrative or take advantage of the community since they can control who says what and stop anyone from calling them out.

I'm not saying all comments should be allowed. Of-course comments that include derogatory or outright negative statements should be deleted since they go against guidelines. I'm saying authors shouldn't be able to censor anyone who doesn't fit their viewpoint.

In the spirit of the article, I'll get the discussion started in the comments below.

About the Author 👨🏾‍💻

I'm Gregory Gaines, a simple software engineer @Google who's trying to write good articles. If you want more content, follow me on Twitter at @GregoryAGaines.

Now go create something great! If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

Stop Using .env Files Now!

Gregory Gaines — Mon, 19 Sep 2022 21:04:49 +0000

Hello Reader
The problem with .env files

Storing the .env file
Updating a secret config
Versioning

Config servers to the rescue

Solving: Storing the .env file
Solving: Updating a secret
Solving: Versioning

More Pros of a Config Server

Automatic Secret Rotation
VPC Endpoints
Audit Logs

About the Author

Hello Reader 👋🏽

I've worked on huge enterprise systems and I'm disappointed to see 99% of all JavaScript tutorials tell you to use a .env for production config and secrets which is dumb.

It's time to correct this behavior plaguing the community. Let's explore the problem with .env files and the ultimate solution.

The problem with .env files 🚫

1. Storing the .env file

The problem is well... It's a file. You are not supposed to store your "production" file in your repo; where do you put it? Directly in the VM root? What about Docker containers, do you bake your secrets directly in the image? If the image leaks, everyone has access to your secrets.

2. Updating a secret config

What happens if you need to update a database password? Whoever updates the .env will have access to every secret in the file. I don't even have to explain why this is bad. Every time a config has to be updated whoever is updating it can see EVERY secret.

The updater has access to all your secrets

3. Versioning

Let's say you are deploying a new feature that requires updating your config / secret variables, something goes wrong and the application gets rolled back.

Uh-oh does anyone remember the last values we had in the .env? We have no history and the application requires the values we just deleted/overwrote.

Config servers to the rescue 🦸‍♂️

The perfect solution to all these issues is using a config server. A config server is an externalized application for storing configs and secrets. It's considered the central hub for managing secrets across environments.

Multiple cloud services can function as a config server like AWS Parameter Store, Google Secrets Manager, or HashiCorp Vault for my open-source enthusiasts.

Once you create a secret or config, most of the time you are given a URL like https://app.com/config/DB_PASSWORD/v1.

Let's see how a config server solves all the issues with .env files.

Solving: 1. Storing the .env file

With a config server, all the secrets are centralized in one place, encrypted, and can only be accessed by applications and users you approve.

No plain files in sight!

Solving: 2. Updating a secret

With a config server, instead of updating a secret, you create a new version. After creating a new version, you update your secret URL like .../config/DB_PASSWORD/v2 or .../config/DB_PASSWORD/v3.

Adding a new secret version

Solving: 3. Versioning

Like with solution 2, most config servers have automatic versioning. If you need to update a secret, create a new version and update the config URL in the application. If the application gets rolled back, it will automatically use the last config URL you had in place.

This way secrets are protected and your applications can get rolled back with no issues with the previous secrets.

Look at all those secret versions

More Pros of a Config Server ✅

Automatic Secret Rotation

Secrets can become stale which can lead to your systems becoming compromised! A centralized config like AWS provides automatic Secret Rotation.

If you team or org all pull the same config, they will automatically get updated with the latest values. No need to send it over slack, no need to get a "trusted" dev, or having the possibility of forgetting to update one of your .env files. Easy and painless!

VPC Endpoints

A config server is usually hosted on a VPC which provides a localhost like connection for your services. This allows the ability to pull secrets without them ever having to touch the internet (virtually no latency), nor allowing outsiders to query the server.

Audit Logs

Did a secret get leaked? Config servers usually carry audit logs so you can check when or where a secret was accessed.

Does an updated config cause an error? Check when it was last updated and if needed, preform a global update for all your services. No plain text file editing needed.

Final Thoughts 💭

I hope now developers will start using centralized configs for their production services. .env files are unreliable and have no access management, versioning, or safe updates.

I'm not saying .env file don't have a purpose. They can be used for local or development-oriented environments.

What I'm trying to say is don't store valuable secrets in simple files, especially if my data is in your service.

About the Author 👨🏾‍💻

I'm Gregory Gaines, a simple software engineer @Google who's trying to write good articles. If you want more content, follow me on Twitter at @GregoryAGaines.

Now go create something great! If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

Build Your Own Google Like Autocomplete Using React And JavaScript

Gregory Gaines — Wed, 20 Apr 2022 14:30:19 +0000

Howdy Reader 👋🏽

It's the 1990's and you've just come up with a brilliant idea! What if I built a sort of "search engine" for internet users to discover sites and named it Foogle? You build the engine but users don't know what to search. To make matters worst, the majority of users are spelling things wrong causing skewered results.

You decide to build an autocomplete to mitigate both issues. Luckily, you remember your college course on algorithms and data structure and the Trie data structure pops into your head.

Today, we are going to implement the autocomplete feature for your company Foogle using the trie data structure.

Here is a demo and source:

gregorygaines / foogle-autocomplete

An autocomplete system written in JavaScript for the Foogle company.

Foogle Autocomplete

The system is written in JavaScript and autocomplete suggestions are stored in a trie tree. When a user types a search query, the query is used as a prefix to find other suggestions that start with the query.

View on GitHub

Prerequisites

Basic knowledge of React and hooks.
Basic understanding of data structures.
Proficient in JavaScript.

What is Autocomplete 🤔

Autocomplete is a search engine feature where the search engine predicts the user's search and provides suggestions.

Project Design ✏️

Our project is a search engine whose functionality is exposed through a search bar. When a user types into the search bar, a back-end call is made for autocomplete suggestions based on the search query.

In the back-end, the user's search query is treated as a prefix used to find suggestions with the same prefix. The gathered sentences are lexicographically sorted (to make them easier to read) and returned to the front end.

The front-end displays the autocomplete results to the user.

Building the Front-End 🖥️

I'm not gonna spend too much time on this section because it's not the meat and potatoes of this article. I will, however, go over the parts that matter.

The main files to focus on are: App.js and SearchBar.js.

SearchBar.js contains the code for the search bar component, the "Foogle Search" and "I'm feeling lucky" buttons, and autocomplete results wrapper.

const SearchBar = (props) => {
  // Check if we have any autocomplete results
  const hasSearchResults = props.autocompleteResults.length > 0;

  return (
    <>
      <input type="text" onChange={(e) => {
        if (props.handleOnChange) {
          props.handleOnChange(e);
        }
      }} value={props.searchQuery} />
      </div>
      { /* Display autocomplete results */ }
      {
        props.autocompleteResults.map((autocompleteResult) => {
          return <li>autocompleteResult</li>;
      }
    </div>
  </>

It consumes three props:

props.handleOnChange - Method to call when the input element is changed.
props.searchQuery - Value to fill the input.
props.autocompleteResults - Values to fill the autocomplete.

Controlled Component 🎛️

The handleOnChange and searchQuery props convert the input element into a controlled component. HTML form element usually maintains their own state which goes against React's methodologies.

In response, we set a hook as the single source of truth which is passed as the value for the input. A method is passed to handle the onChanged event for the input and updates the hook containing the input's value whenever the input is changed. This ensures that React stays in control.

// Hook representing the value of the input
const [value, setValue] = useState("");

const handleInputChange = (e) => {
  // Get value from the change
  const inputValue = e.target.value;

  // Update the hook to new value
  setValue(inputValue);
}

// Pass value and onChange handler
return <input value={value} onChange={handleInputChange} />

App.js is the main point of the code. It contains the Foogle home page, the search bar component and it's hook, and makes the call for autocomplete results.

const App = () => {
  // The value of the search bar
  const [searchQuery, setSearchQuery] = useState("");
  // The hook to retrieve autocomplete results using "searchQuery"
  const autocompleteResults = useAutocomplete(searchQuery);

  // The onChange handler for the search input
  const handleSearchInputChange = (e) => {
    setSearchQuery(e.target.value);
  }

  return (
    {/* Pass hook value, onChange handler, and autocomplete results */}
    <SearchBar searchQuery={searchQuery} handleOnChange={(e) => {
        handleSearchInputChange(e);
    }} autocompleteResults={autocompleteResults} />
  );
}

Designing The Autocomplete System 🏗️

The autocomplete results come from the useAutocomplete hook shown in App.js. Here's a look into the hook.

const useAutocomplete = (searchQuery) => {
  // Holds autocomplete results
  const [autocompleteResults, setAutocompleteResults] = useState([]);

  // Run when 'searchQuery' changes
  useEffect(() => {
    // If the search query is a valid string, fetch suggestions
    if (searchQuery.trim().length > 0) {
      // TODO Fetch suggestion from database
      // setAutocompleteResults();
    } else {
      // Clear autocomplete results on empty search query
      setAutocompleteResults([]);
    }
  }, [searchQuery]);

  // Return autocomplete results
  return autocompleteResults;
}

Let's pretend we have a database full of autocomplete suggestions. suggestionsDatabase.js represents this database.

const suggestionsDatabase = [
  "How to get a job at Google",
  "How to get gum out of hair",
  "How to get people to like me",
  "How to get a job at Amazon",
  "Sasuke is a trash character",
  "How high is the empire state building",
  "Her by Tyler The Creator"
  ...
];

When users type a search query, we have to find all suggestions that start with the query. The problem is how can we filter through all suggestions without checking each string one by one? Individually checking is extremely slow and has a time complexity of O(n) where n is the number of suggestions.

What if we had millions of suggestions? A search could end up with an O(10^9) time complexity. That would take hours or potentially days to run. Not to mention the millions of Foogle users hitting the database at the same time. We would have a terrible user experience! Luckily, we have the Trie data structure that's made to solve this very problem!

What is a Trie 🌳

A trie or prefix tree is a tree data structure made for quick retrievals of stored keys. In our case, our trie will store suggestions. Each node represents a letter in the alphabet and inside each node contains a Map that maps letters of the alphabet to other nodes which continue the cycle.

Here is the structure for a node.

class TrieNode {
  // Map for mapping letters to other child nodes
  children
  // Is this node the end of a string
  isEndOfString

  constructor() {
    this.children = new Map();
    this.isEndOfString = false;
  }
}

A node contains a Map for mapping letters to other child nodes and a boolean to indicate this node is the last letter of a string. Below is a visual representation of a trie.

Starting from the root, traversing down each branch node creates a representation of a string. A string is inserted into a trie letter by letter and each letter represents a level down in the trie.

For example, take the string there from the image above. Start with the first letter t and the root node. Check the root node's children for a mapping for the letter t to a child node. If it doesn't exist, create it and move to it. If it does, then move to it.

Now we are in a child node in the next level of the trie. We take the next letter h and repeat the process again. If the current node's children contain a mapping for h move to it, if not, create it and move to it. We move on to e and repeat the process till we get to the last letter e. We set isEndOfString true on the current node to indicate we ended a string on this node.

Code speaks louder than words so let's write some. Here is the code for the trie.

class Trie {
  rootNode

  constructor() {
    // Create root node
    this.rootNode = new TrieNode();
  }

  // Returns if the trie contains a string
  contains = (str) => {

  }

  // Inserts a string into the trie
  insert = (str) => {

  }

  // Get all words with prefix
  getWords = (prefix) => {

  }
}

Let's fill in the trie functions starting with insert since we went over the process.

Inserting a string

To recap inserting a string, start from the root node. Traverse down a child node for each letter in the string and mark the final node as isEndOfString.

insert = (str) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  // Loop for each char in the string.
  for (let level = 0; level < length; level++) {
    // Get the current char
    const char = str.charAt(level);

    // Check if the current node has a mapping
    // of the current char to a child node.
    // If not, create a node and map it.
    if (!crawlNode.children.has(char)) {
      crawlNode.children.set(char, new TrieNode());
    }

    // Traverse to the next mapped node in the trie.
    crawlNode = crawlNode.children.get(char);
  }

  // Set the current node as the end of the string.
  crawlNode.isEndOfString = true;
}

The time complexity is O(n) where n is the length of the string being inserted.

Searching a string

Searching if the trie contains a string is a similar process to insertion. We traverse the levels of the trie for each char in a string. If we encounter a node without a mapping of the current char, then the trie doesn't contain the string.

If we fully traverse a string and the final node doesn't have isEndOfString set as true, then the string isn't in the trie.

contains = (str) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels we need
  // to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  // Loop for each char in the string.
  for (let level = 0; level < length; ++level) {
    // Get the current char
    const char = str.charAt(level);

    // If the current node doesn't have a mapping
    // for the current char, the string hasn’t
    // been inserted.
    if (!crawlNode.children.has(char)) {
      return false;
    }

    // Traverse to the next mapped node in the trie.
    crawlNode = crawlNode.children.get(char);
  }

  // Return if the current node
  // is the end of the string.
  return crawlNode.isEndOfString;
}

The time complexity for insertion is O(n) where n is the length of the string being inserted.

Retrieving all words with a prefix

Our problem was searching for autocomplete suggestions that have the same prefix as the user's search query. The trie solves our problem by efficiently storing autocomplete suggestions and allows us to quickly search them all at the same time because strings with the same prefix overlap the same nodes.

We are now going to create a method to retrieve all words from the trie that start with a prefix.

This is gonna be complex so pay attention. Imagine we have the strings below inserted in a trie.

is water blue
is fire hot
is sasuke trash

A user types the search query is which is a prefix to all three strings above. To find all words with the prefix of is, we need the child node of the last char in the prefix. In our case, we need the node for the s char when traversed from the root node with the i char.

Once we have the prefix node, we create a recursion function to build strings for each child node and their child nodes till we run out of nodes. Confused yet? It's easier to explain with code.

First, we need the node of the last char in the prefix. Let's add a parameter to the contains function to return the node instead of a boolean.

contains = (str, returnNode) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels we need
  // to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  for (let level = 0; level < length; ++level) {
    const ch = str.charAt(level);

    if (!crawlNode.children.has(ch)) {
      return false;
    }

    crawlNode = crawlNode.children.get(ch);
  }

  // Return the current node
  if (returnNode) {
    return crawlNode;
  }

  return crawlNode.isEndOfString;
}

With the prefix root node, we can create the boilerplate for our getWords function.

  // Get all words with prefix
  getWords = (prefix) => {
    // Get root node of prefix
    let prefixRootNode = this.contains(prefix, true);

    // The prefix isn't in the trie.
    if (!prefixRootNode) {
      return [];
    }

    // Hold the results
    let result = [];

    // Call our recursion function from the prefix root.
    this.#_getWordsHelper(prefixRootNode, prefix, result);

    // Sort and return the results
    return result.sort();
  }

  // Recursion function to get all words that start from
  // node.
  #_getWordsHelper = (root, currString, result) => {

  }

To get all strings stored from a node, we use DFS recursion on every child node inside the current node we are on and repeat the process on it's child nodes.

Here's how it works. When _getWordsHelper is called, it checks if the current node is null, if so we ran out of nodes for the branch and stop; This is a base case.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  } 
}

Next, it checks if the current node has isEndOfString set. If so, it add currString to the result array since it represents a complete string.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  } 

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }
}

Next, it takes every child node of the current node and calls itself on each of them, using the child node as the new root while appending the char the child node maps to onto currString for the new call to continue building the string.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  }

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }

  // Loop over each mapping in the children
  for (let [key, value] of root.children) {
    // Append the key char to 'currString' and
    // recur on the new node.
    this.#_getWordsHelper(value, currString + key, result);
  }
}

Following this process will eventually store every single string contained in trie that starts from the prefix root node. The full code for getWords is:

// Get all words with prefix
getWords = (prefix) => {
  // Get root node from prefix
  let prefixRootNode = this.contains(prefix, true);

  // The prefix isn't in the trie.
  if (!prefixRootNode) {
    return [];
  }

  // Hold the results
  let result = [];

  // Call our recursion function from the prefix root.
  this.#_getWordsHelper(prefixRootNode, prefix, result);

  // Sort and return the results
  return result.sort();
}

// Recur on the children of the current node
// and add any complete strings to the result
// array.
#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  }

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }

  // Loop over each mapping in the children
  for (let [key, value] of root.children) {
    // Append the key char to currStirng and
    // recur on the current node.
    this.#_getWordsHelper(value, currString + key, result);
  }
}

The time complexity for getting all prefixes is O(n) where n is the number of nodes in the trie.

Connecting our suggestions database

To represent the autocomplete suggestions database, we insert all the suggestionsDatabase strings into the trie. Let's add a constructor to Trie that accepts strings and inserts them into itself.

class Trie {
...
  constructor(strs) {
    this.rootNode = new TrieNode();

    // Insert strings into the trie.
    strs.forEach((str) => {
      this.insert(strs);
    });
  }
...
}

Going back to the front-end and inside the useAutocomplete.js file. Before the class declaration, init the Trie class and pass the suggestionsDatabase strings. This will function as our pseudo suggestions database.

import { suggestionsDatabase } from "./suggestionsDatabase";

// Pretend we connected to our database.
const trie = new Trie(suggestionsDatabase);

const useAutocomplete = (searchQuery) => {
...

Now inside the useEffect method, we add code to retrieve all words with the searchQuery as a prefix from the trie.

const trie = new Trie(suggestionsDatabase);

const useAutocomplete = (searchQuery) => {
  // Holds autocomplete results
  const [autocompleteResults, setAutocompleteResults] = useState([]);

  // Run when 'searchQuery' changes
  useEffect(() => {
    // If the search query is a valid strings, fetch suggestions
    if (searchQuery.trim().length > 0) {
      // Fetch suggestion from database
      setAutocompleteResults(trie.getWords(searchQuery));
    } else {
      // Clear autocomplete results on empty search query
      setAutocompleteResults([]);
    }
  }, [searchQuery]);

  // Return autocomplete results
  return autocompleteResults;
}

Typing into the search bar will return all autocomplete suggestions that share a common prefix with the search query!! 😁

The autocomplete in action!

Final Thoughts 💭

We created a search bar input and maintained its state with a hook. We have mullions of autocomplete suggestions to filter when a user searches. In response, we construct a trie to store suggestions that can easily be retrieved for an O(n) time complexity instead of an (10^9) time complexity.

The trie solves our problem by efficiently storing autocomplete suggestions and allows us to quickly search words with the same prefix because strings with the same prefix overlap the same nodes. When a search query is entered, we retrieve all autocomplete suggestions that are prefixed with the query and show them to the user!

About Me 👨🏽‍💻

I'm Gregory Gaines, a fun-loving software engineer @Google who loves writing entertaining articles. If you want more content, follow me on Twitter at @GregoryAGaines.

After reading this maybe you should apply to Google 😆! If you have any questions, hit me up on Twitter (@GregoryAGaines).

Legal: I am a Google employee; all opinions are my own. This post is not an endorsement nor contains any proprietary knowledge.

The Only JavaScript Sorting Guide You'll Ever Need

Gregory Gaines — Fri, 15 Apr 2022 18:19:30 +0000

Hello Reader
JavaScript's sort() function

Implementation History

Sorting Primitives

Array of Strings
Array of Numbers

Compare Function
Descending Order

Sorting an Array of Objects
Final Thoughts

Hello Reader 👋🏽

I was tired of searching on Google when I was unsure of how to sort whatever data I'm using in JavaScript, so I decided to write it all in one place.

Today, we are going to learn about sorting in JavaScript. Starting with the history and algorithm used for .sort(). Then learning how to sort primitives and objects. Let's jump in!

JavaScript's sort() function 📏

The .sort() function sorts an array in-place (meaning no copy is made) and returns the sorted array. We can't modify the algorithm used by .sort(), but we can modify how it compares array elements by passing a compare function.

// Native, without a compare function
sort()

// With an arrow pointing compare function
sort((a, b) => {
 ...
})

// Passing a compare function
sort(compareFn)

Implementation History

In Chrome, back in the ye-old days, the sorting algorithm wasn't as good as today. One of its previous implementations included insertion sort O(n²) 🤢.

Today we are in a better state with a modification of Merge Sort named Tim Sort O(n log n) 😊. Initially created by Time Peters as an adaptive stable Merge Sort variant.

A stable sorting algorithm means if two values of the same value sit next to each other, they maintain the same order after sorting. You'd be surprised how many algorithms depend on this.

Sorting Primitives

Let's go over how to sort primitives with .sort().

Sorting an Array of Strings

The sort() function works how you'd expect for strings.

const names = ["Darui", "Bee", "Naruto", "Ada", "Sasuke", "Baki", "A"];

console.log(names.sort());

// Output: ["A", "Ada", "Baki", "Bee", "Darui", "Naruto", "Sasuke"]

JavaScript by default sorts in Lexicographical order. Lexicographical order means sorted alphabetically sort of like a dictionary. If two strings are equal, then the shortest one is put first.

// Lexicographical order
const str = ["aab", "ba", "aac", "bab", "aaa", "Aab", "aaaa"];

// Results
"Aab" // Uppercase letters take precedence
"aa|a"
"aa|aa" // Is equal to "aaa" but is longer
"aa|b" // The 3rd char 'b' comes the third char 'a' in the strings above.
"aa|c" // The last char 'c' comes after 'b'
"ba" // The first char 'b' comes after 'a' in the above strings
"bab"

Sorting an Array of Numbers 🧮

Using .sort() on numbers is a bit tricky. It DOES NOT work natively.

const scores = [9, 80, 19, 4, 20, 53];

// Wrong ❌
console.log(scores.sort());

// Wrong order 👎🏽
// Output: [19, 20, 4, 53, 80, 9]

By default, JavaScript sorts in Lexicographical order. Great for strings but terrible for numbers. We have to pass a compare function.

Who gets sorted first?

Compare Function

Compare function interpretation

The compare function returns an integer which .sort() uses to determine the order when comparing elements.

function compareNumbers(a, b) {
  if (a < b) {
    return -1; // sort a before b
  } else if (a > b) {
    return 1; // sort a after b
  }

  return 0; // keep a and b in the same order
}

When two elements are passed to the compare function, if it returns less than 0, a is put first. If the result is greater than 0, b is put first. If the result is equal to 0, keep a and b in the same order. Ex. a(3) - b(2) is 1 which puts b(2) in front of a(3).

To properly sort numbers, we introduce a compare function to sort numbers in ascending order.

let scores = [9, 80, 19, 4, 20, 53];

// Sort in ascending order ✅
scores.sort((a, b) => {
  return a - b;
});

console.log(scores);

// Output: [4, 9, 19, 20, 53, 80]

Descending Order

Descending order is an easy 1 line change. Instead of using a - b, use b - a to reverse the order. Take our a(3) - b(2) example from earlier. If we change it to b(2) - a(3), we get -1. This instead puts a(3) in front of b(2).

let scores = [9, 80, 19, 4, 20, 53];

// Sort in descending order
scores.sort((a, b) => {
  return b - a;
});

console.log(scores);

// Output: [80, 53, 20, 19, 9, 4]

Sorting an Array of Objects 🏎️

In JavaScript, an object is a variable with a collection of properties in key:value pairs.

// Array of objects with two properties, 'name' and 'titansDefeated'.
const characters = [{
    name: 'eren',
    titansDefeated: 1
  },
  {
    name: 'mikasa',
    titansDefeated: 20
  },
  {
    name: 'levi',
    titansDefeated: 90
  },
  {
    name: 'armin',
    titansDefeated: 10
  },
];

Since objects have multiple properties, we pass a compare function to sort by the property we want.

Sorting by the amount of titansDefeated in ascending order.

const characters = [{
    name: 'eren',
    titansDefeated: 1
  },
  {
    name: 'mikasa',
    titansDefeated: 20
  },
  {
    name: 'levi',
    titansDefeated: 90
  },
  {
    name: 'armin',
    titansDefeated: 10
  },
];

characters.sort((a, b) => {
  return a.titansDefeated - b.titansDefeated;
});

console.log(characters);

// Output: [{
//  name: "eren",
//  titansDefeated: 1
// }, {
//  name: "armin",
//  titansDefeated: 10
// }, {
//  name: "mikasa",
//  titansDefeated: 20
// }, {
//  name: "levi",
//  titansDefeated: 90
// }]

Sorting by the amount of titansDefeated in descending order.

const characters = [{
    name: 'eren',
    titansDefeated: 1
  },
  {
    name: 'mikasa',
    titansDefeated: 20
  },
  {
    name: 'levi',
    titansDefeated: 90
  },
  {
    name: 'armin',
    titansDefeated: 10
  },
];

characters.sort((a, b) => {
  return b.titansDefeated - a.titansDefeated;
});

console.log(characters);

// Output: [{
//  name: "levi",
//  titansDefeated: 90
// }, {
//  name: "mikasa",
//  titansDefeated: 20
// }, {
//  name: "armin",
//  titansDefeated: 10
// }, {
//  name: "eren",
//  titansDefeated: 1
// }]

Sorting by names in lexicographical order.

const characters = [{
    name: 'eren',
    titansDefeated: 1
  },
  {
    name: 'mikasa',
    titansDefeated: 20
  },
  {
    name: 'levi',
    titansDefeated: 90
  },
  {
    name: 'armin',
    titansDefeated: 10
  },
];

// Sort names in case-insensitive
// lexicographical order
characters.sort((a, b) => {
  // Convert to uppercase so we don't have
  // to worry about case differences.
  const nameA = a.name.toUpperCase();
  const nameB = b.name.toUpperCase();

  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});

console.log(characters);

// Output:[{
//  name: "armin",
//  titansDefeated: 10
// }, {
//  name: "eren",
//  titansDefeated: 1
// }, {
//  name: "levi",
//  titansDefeated: 90
// }, {
//  name: "mikasa",
//  titansDefeated: 20
// }]

Levi said "sort faster"

Final Thoughts 💭

Here's everything you need for sorting in JavaScript all in one place. In Chrome, .sort() is implemented using the Tim Sort algorithm. By default .sort() sorts in lexicographical order, great for strings but not so much for anything else. We pass a compare function for numbers and objects to define the sorting order.

I'm Gregory Gaines, a goofy software engineer @Google who's trying to write good articles. If you want more content, follow me on Twitter at @GregoryAGaines.

Now go create something great! If you have any questions, hit me up on Twitter (@GregoryAGaines); we can talk about it.

Thanks for reading!

Playing Breaking Bad Quotes From a Phone Call Using Node.JS and Twilio ⚗️

Gregory Gaines — Thu, 14 Apr 2022 17:21:29 +0000

Howdy Reader 👋🏽

Have you ever been in a situation where you wanted to hear quotes from your favorite show but didn't have a way to? I recently watched Breaking Bad and Walter's and Jesse's iconic voices still bounce around in my head.

Today, I'll be teaching you how to set up a number that automatically plays Breaking Bad quotes when called, or you can use it for something lame like setting up an automated support line for a product, startup, or whatever capitalistic endeavor you have in mind. 🥱

Call this number for a Demo: +1(318) 490-4496

Prerequisites ✋🏽

Basic JavaScript Knowledge.
A Twilio Account
A recent Node.js installation.

What is Twilio? 📱

Twilio is a company that provides APIs for various communicating needs like phone calls, text messaging, or P2P video streaming.

We are using the Programmable Voice API that exposes functionality for playing a voice or audio.

Project Design 🏗️

Let's go over the design!

A user first calls our number, then Twilio calls an endpoint on our express server which tells Twilio "Hey, answer the call and return this audio". Twilio says ok, then plays the audio back to the caller.

Project Setup

Let's start cooking our project.

Twilio API Keys 🔑

Let's kick off by getting our Twilio API keys, we'll need them later for testing. If you don't have a Twilio account, here’s the sign-up page (don't worry it's not an affiliate link). Don't forget to generate a free phone number.

The console should show two tokens connected to your account info, the Account SID and Auth Token.

Adding Environment Variables 🤫

One of the packages we installed was dotenv. Dotenv allows us to define a .env file for variables or sensitive keys (depending on who you ask) that are loaded into process.env.

Open the .env file and add your Twilio API keys and your generated phone number.

TWILIO_ACCOUNT_SID=<YOU_ACCOUNT_SID>
TWILIO_AUTH_TOKEN=<YOUR_AUTH_TOKEN>
TWILIO_NUMBER=<YOUR_GENERATED_TWILIO_NUMBER> # Ex. +14045555555

Creating Express.js Server

To handle Twilio asking "what should I do?", we need an Express.js server. Create an empty directory and init an empty npm project and set whatever configs you want except change "entry" to app.js.

npm init

Then run the NPM command below to install our required packages.

npm install express dotenv twilio ngrok

Create the below folder structure.

├── public/ - Public static files
├── routes/ - HTTP routes
    └── voice.js - Twilio API endpoints
├── .env
├── app.js - HTTP server definition
├── package.json
├── package-lock.json

Let's add some server code to app.js!

const express = require('express');
const path = require('path');
const http = require('http');

// Pull environment variables 
require('dotenv').config();

// Init Express
const app = express();
app.use(express.json());
app.use(express.urlencoded({extended: false}));
app.use(express.static(path.join(__dirname, 'public')));

// Set port
const port = '3000';
app.set('port', port);

// Create HTTP server
const server = http.createServer(app);

// Start server on port
server.listen(port, () => {
  console.log("Started server");
});

module.exports = app;

Run this command to start the server.

node app.js

Adding Audio Files 🎤

As per our requirements, let's gather some audio files to play when someone calls our number. You already know I'm doing Breaking Bad quotes but you can use whatever you want, I'm not your boss.

I used this site to download Breaking Bad quotes.

After getting your audio files, place them in the public folder. If you don't want your audio files exposed publicly, you can create another folder and relocate them.

Create Audio Response Endpoint

When someone calls our Twilio number, we direct Twilio to our POST endpoint that tells Twilio how to respond to the caller using TwiML, Twilios markup language for commands.

Navigate to the routes/voice.js file. We are adding an POST endpoint named /voice which randomly selects a quote, then creates and returns a TwiML command telling Twilio to play this file.

const express = require('express');
const VoiceResponse = require('twilio').twiml.VoiceResponse;
const fs = require('fs');

// Create router
const router = express.Router();

// Create a 'POST' endpoint named '/voice'
router.post('/voice', (req, res) => {

  // Get all the files in the /public folder 
  // then filter for only .mp3 files.
  const audioFiles = fs.readdirSync('./public').filter((file) => {
    return file.match(new RegExp('.*\.(mp3)', 'ig'));
  });

  // Choose a random .mp3
  const randomAudioFile = audioFiles[Math.floor(Math.random() * audioFiles.length)];

  // Create a voice response
  const voiceResponse = new VoiceResponse();

  // Add a pause because the audio starts too quickly
  // and the person calling might miss the beginning.
  voiceResponse.pause({
    length: 1,
  });

  // Generate a TwiML command that says 
  // "Play this audio file once".
  voiceResponse.play({
    loop: 1
  }, randomAudioFile);

  // Send response to Twilio
  res.type('text/xml')
    .status(200).send(voiceResponse.toString());
});

module.exports = router;

Now attach the route to our server by editing app.js.

const voiceRouter = require('./routes/voice');
app.use(voiceRouter);

Make sure to restart your server on code changes.

Testing '/voice' Endpoint 🔬

Before attaching our endpoint to Twilio, we'd better test it first unless you're a bad programmer then by all means skip this section. Just tell me what your product is so I know NOT to add my debit card to it 🤣.

To check if the endpoint path works, use an HTTP client like Postman to send a POST request to localhost:3000/voice. You should see something like this:

<?xml version="1.0" encoding="UTF-8"?>
<Response>
    <Pause length="1"/>
    <Play loop="1">who_knocks.mp3</Play>
</Response>

To test the functionality of our endpoint, we create a Twilio function to call a number using the command from the /voice endpoint. If your Twilio account isn't activated, the only number you can call is the one you created your account with.

Before we can do that, Twilio can't run commands that run on localhost. Doesn't matter if we're testing or not. Luckily, there is a tool called Ngrok, a reverse proxy that exposes our localhost:3000 express server to the internet like it's an actual server!

Navigate to the app.js file. In the server.listen command's callback, add code to connect our express server to the internet then restart the server.

const ngrok = require('ngrok');

// Listen on port
server.listen(port, () => {
  console.log("Started server");

  // Create a public url for our
  // `localhost:3000` express server.
  ngrok.connect({
    addr: 3000, // Our localhost port
  }).then((ngrokUrl) => {
    console.log("Connected to url: " + ngrokUrl);
  });
});

You should see something like:

Connected to url: https://xxxx-xx-xx-xxx-xx.ngrok.io

Now we create the Twilio code to test our command! Create a Twilio client using the TWILIO_ACCOUNT_SID and TWILIO_AUTH_TOKEN environment variables we added earlier.

const twilio = require("twilio");

// Listen on port
server.listen(port, () => {
  console.log("Started server");

   // Create Twilio client
  const twilioClient =
     new twilio(process.env.TWILIO_ACCOUNT_SID, process.env.TWILIO_AUTH_TOKEN);
...

With our Twilio client, we send a command to call a phone number using the command from the /voice endpoint.

// Listen on port
server.listen(port, () => {
  console.log("Started server");

  // Create a public url for our
  // `localhost:3000` express server.
  ngrok.connect({
    addr: 3000,
  }).then((ngrokUrl) => {
    console.log("Connected to url: " + ngrokUrl);

    // Append voice endpoint to ngrokUrl
    const voiceUrl = `${ngrokUrl}/voice`;

    // Create Twilio client
    const twilioClient = new twilio(process.env.TWILIO_ACCOUNT_SID, process.env.TWILIO_AUTH_TOKEN);

    // Call a phone number using the
    // command from the /voice endpoint.
    twilioClient.calls.create({
      to: '<TARGET_PHONE_NUMBER>', // Target number to call
      from: process.env.TWILIO_NUMBER, // Your generated Twilio number
      url: voiceUrl, // The ngrok url that points to the /voice endpoint
      method: 'POST'
    }).then((call) => {
      console.log(call); // Print call log
    }).catch((err) => {
      console.log("Error making call " + err); // Print error
    });
  });
});

After a few seconds, you should get a call playing the selected audio file!! Pretty cool right? 😊

Connect /voice Endpoint to Twilio 🪛

It's time for the moment of truth! We are going to connect our /voice endpoint to Twilio. Login to your Twilio account and navigate to the console. Click 'Explore Products' in the left sidebar.

Scroll down and click 'Phone Numbers'.

Select your Twilio number.

Scroll down to 'Voice & Fax' and add your ngrok url that points to the /voice endpoint as a webhook for 'A CALL COMES IN'.

Call your Twilio phone number and your audio will play right into your ear!!! 👍🏾👍🏾👍🏾

Final Thoughts 💭

Who says T.V rots your brain? Because of Breaking Bad, we learned about system design, creating a server, how to use environment variables, the importance of testing, and most importantly how to cook... code 😉. Hopefully, you've enjoyed the read and taken something from it.

I'm Gregory Gaines, a goofy software engineer who's trying to write good articles. If you want more content, follow me on Twitter at @GregoryAGaines.

Now go create something great! If you create a Twilio app or need some help hit me up on Twitter (@GregoryAGaines) and we can talk about it.

Getting Started With TailwindCSS v3.0 in React

Gregory Gaines — Tue, 12 Apr 2022 16:36:54 +0000

Why TailwindCSS

Say whatever you want about Utility-First CSS frameworks, it's here to stay! Traditional CSS was designed for "monolithic" writing where you gave each component a specific selector which led to code duplication. Seems kinda outdated in the current space of splitting and abstracting components. Techniques like BEM were invented to mitigate some of this damage.

TailwindCSS is one of the premier Utility-First CSS frameworks that automatically generate CSS classes to handle almost every styling use-cases you may encounter. With its built-in design system, which is based on an underlying scale, all your spacings, margins, and paddings are consistent and beautiful. I can go on for hours, but let's get into how to use TailwindCSS.

Creating a React App

Start a new React app by running the command below.

npx create-react-app tailwindcss-app

Installing TailwindCSS

TailwindCSS depends on the following npm packages.

TailwindCSS - The TailwindCSS framework
PostCSS - JavaScript based CSS transformation tool
Autoprefixer - CSS parser that automatically adds vender prefixes

All three can be installed with the following command.

npm install -D tailwindcss postcss autoprefixer

Creating TailwindCSS Config

Configurations for TailwindCSS and PostCSS need to be generated with command below.

npx tailwindcss init -p

This will generate the two files tailwind.config.js and postcss.config.js.

Next, add your code source the the tailwind.config.js config.

module.exports = {
  content: [
    "./src/**/*.{js,jsx,ts,tsx}", // Add code source
  ],
  theme: {
    extend: {},
  },
  plugins: [],
}

tailwind.config.js is also useful for defining custom styles or extending existing styles.

Import TailwindCSS directives

We need to import the TailwindCSS styles into our project. Most default React projects contain an index.css style that's applied to the entire project.

src /
 | - App.js
 | - App.css
 | - index.css
   ...

We import TailwindCSS here since we only have to import it once.

@tailwind base;
@tailwind components;
@tailwind utilities;

Running some TailwindCSS code

Let's add some code and TailwindCSS styling to App.js.

function App() {
  return (
    <section className="px-4 py-24 mx-auto max-w-7xl">
      <div className="grid items-center w-full grid-cols-1 gap-0 mx-auto lg:grid-cols-11 lg:gap-24 xl:w-11/12">
        <div className="col-auto text-center md:col-span-7 lg:text-left">
          <h1 className="mb-4 text-3xl font-bold leading-tight text-gray-900 md:text-4xl md:leading-none tracking-none md:tracking-tight">Ready
            to start your TailwindCSS jurney?</h1>
          <p className="mb-10 text-lg font-light text-gray-500 md:text-xl md:tracking-relaxed md:mb-4">
            Your move!
            Yu-Gi-Oh!
            Your move!
            Yu-Gi-Oh!
            It's time to du-du-du-du-dududududududuel!
            Yu-Gi-Oh! (-Oh! -Oh! -Oh!)
            Your move!
            Yu-Gi-Oh is king of games!
            It's time to du-du-du-du-dududududududuel!
            Yu-Gi-Oh!
          </p>
        </div>
        <div className="col-auto md:col-span-4">
          <form className="mb-6 border-0 rounded-lg shadow-xl">
            <div className="cursor-pointer px-6 py-4 text-center bg-blue-500 text-white font-bold rounded">
              Get started
            </div>
          </form>
        </div>
      </div>
    </section>

  );
}

export default App;

Now start the React app with the below command.

npm run start

You should see something similar below.

Conclusion

Hopefully, you have your TailwindCSS project ready to go. Thanks for reading!

Follow me on Twitter at @GregoryAGaines or my blog at gregorygaines.com

Anime (or any other video) Translator - Chrome extension that automatically translates web videos! 👯

Gregory Gaines — Mon, 11 Apr 2022 23:24:09 +0000

Overview of My Submission

Anime OAV (Anime or any other video) is a chrome extension that automatically translate, transcribes, and generates overlaying subtitles for videos.

gregorygaines / anime-aov-translator

Anime OAV (Anime or any other video) is a Chrome extension that automatically translate, transcribes, and generates overlaying subtitles for videos.

Anime (or any other video) Translator

Anime OAV (Anime or any other video) is a Chrome extension that automatically translate, transcribes, and generates overlaying subtitles for videos.

Features

Audio transcribing
Text translation
Render subtitles onto videos
Multiple text translation engines: Azure Cognitive Translator, Google Cloud Translation

Usage

Set Deepgram and translator engine credentials in src/config.ts.

The translator engine can be changed in src/background.ts like below:

const translator = 
TranslatorFactory.createTranslator(Translators.AZURE);
...
const translator = 
TranslatorFactory.createTranslator(Translators.GOOGLE);

Clone the repo: https://github.com/gregorygaines/anime-aov-translator.git

Start extension dev server: npm run start

Load extension into browser by

Open the Extension Management page by navigating to chrome://extensions.
Enable Developer Mode by clicking the toggle switch next to Developer mode.
Click the LOAD UNPACKED button and select the extension directory dist.

Quirks

The project is in early infancy and the…

View on GitHub

Tech Stack

TailwindCSS - Ui style
Chrome extension
React.js - Front-end library
Deepgram - Transcriber
Azure / Google - Translator
Webpack - Code bundler

Submission Category:

Accessibility Advocates

Why

Sometimes my favorite or interesting shows are produced outside my native language and my only options are to wait for an official or fan-made translation.

I wondered what if I had a way to automatically translate videos outside my native language so I can enjoy them.

Translation isn't the only problem I've had. Sometimes audio can be hard to understand, and I think, if only I had a way to transcribe what everyone is saying.

My extension solves both of the issues above and increases awareness of issues that come with accessibility.

How does it work

Terminology

Below is a short description on how a chrome extension works.

Chrome extension diagram by Aryclenio Barros

Content Scripts - Code that runs on the page the user is currently viewing. Commonly used for operating on the DOM and interacting with the current page. Because of security concerns, some actions can't be preformed on content scripts and must be done in a background script.
Background Scripts - Code that runs in a service worker in the background and can't interact with the current page or DOM. Commonly used for long lived tasks or managing state across the extension. It can be thought of as a back-end of sorts for the extension. To communicate, the background and content scripts can register listeners to pass messages between each other. Since background scripts can preform actions content scripts can't, certain actions are executed there then passed to the content script.

Translating / Transcribing

The background script captures the current tabs audio then passes the audio to Deepgram for transcription.

const transcriber = 
SpeechRecognizerFactory
.createSpeechRecognizer(SpeechRecognizers.Deepgram);

After transcribing the audio, the extension uses one of its multiple translation engines to translate the text. For now, only Azure and Google are implemented.

const translator = 
TranslatorFactory.createTranslator(Translators.AZURE);
...
const translator = 
TranslatorFactory.createTranslator(Translators.GOOGLE);

The translated text is then sent to the client as a message.

const clientMessage = {
  command: "draw_text",
  data: translated,
}

chrome.tabs.sendMessage(activeTabId, clientMessage, (response) => {
  console.log("Sending text to client: " + translated);
});

Subtitles

Because of needed configurations, certain domains are white-listed for translations / transcriptions. When the client encounter a white-listed domain, the content script pulls the needed configuration to find the video player container and its dimensions and position, then draws a canvas overlay for displaying subtitles.

const videoContainerSelector = {
  crunchyroll: "#showmedia_video_box",
}

const videoContainer = queryElement(crunchyroll);
const containerPos = getPos(videoContainer);
const containerDim = getDim(videoContainer);

renderSubtitleCanvas(containerPos, containerDim);

The content script then listens for subtitles from the background script so it can render them on the canvas.

chrome.runtime.onMessage.addListener(
  (request, sender, sendResponse) => {
    switch (request.command) {
      case 'draw_text':
        console.log("Received command to draw text: " + request.data);
        drawTextToCanvas(request.data);
        sendResponse(true);
        return true;

      default:
        console.log("Unknown client command: " + request.command);
    }

    return true;
  },
);

Features

Audio transcribing
Text translation
Render subtitles onto videos
Multiple text translation engines: Azure Cognitive Translator, Google Cloud Translation

Roadmap

Ability to change complex options without modifying code
Increase transcribing accuracy
Add more transcribing engines
Ability to customize subtitle font
Clean up code!!

Screenshots

Conclusion

Not too bad for three days of work huh? This was an incredible project to work on. Sadly, I learned about the hackathon too late, but I had fun regardless.

I want to continue updating the extension if there is a community interest to keep it alive. Open source contributions are extremely encouraged. Thanks for reading!

How to Hash and Salt Passwords in Golang Using SHA-512 and Why You Shouldn’t 😤

Gregory Gaines — Fri, 08 Apr 2022 17:25:54 +0000

Hashing and salting passwords is an industry standard for protecting passwords for any respectable service. One option is using SHA-512 that computes quickly. The downside is attackers can take advantage of this with computational power and crack your passwords 😬.

Using Bcrypt is a better option

Algorithms like SHA are fast and efficient, allowing attackers to quickly brute force a password match. Not a very good choice for security, luckily there is another hashing algorithm called Bcrypt which is designed for hashing passwords slowly.

This frustrates attackers because passwords can't be brute forced and an increase in computational power will do little to help. Learn more on my article on hashing passwords with Bcrypt.

Hashing Steps

Convert password string to a byte slice
Generate random salt of 16 bytes (SHA2-crypt methods in Linus, BSD Unixes, and Solaris use 16 bytes)
Append salt to password slice
Hash the resulting concatenation

Implementation

package main

import (
  "crypto/rand"
  "crypto/sha512"
  "encoding/hex"
  "fmt"
)

// Define salt size
const saltSize = 16

// Generate 16 bytes randomly and securely using the
// Cryptographically secure pseudorandom number generator (CSPRNG)
// in the crypto.rand package
func generateRandomSalt(saltSize int) []byte {
  var salt = make([]byte, saltSize)

  _, err := rand.Read(salt[:])

  if err != nil {
    panic(err)
  }

  return salt
}

// Combine password and salt then hash them using the SHA-512
// hashing algorithm and then return the hashed password
// as a hex string
func hashPassword(password string, salt []byte) string {
  // Convert password string to byte slice
  var passwordBytes = []byte(password)

  // Create sha-512 hasher
  var sha512Hasher = sha512.New()

  // Append salt to password
  passwordBytes = append(passwordBytes, salt...)

  // Write password bytes to the hasher
  sha512Hasher.Write(passwordBytes)

  // Get the SHA-512 hashed password
  var hashedPasswordBytes = sha512Hasher.Sum(nil)

  // Convert the hashed password to a hex string
  var hashedPasswordHex = hex.EncodeToString(hashedPasswordBytes)

  return hashedPasswordHex
}

// Check if two passwords match
func doPasswordsMatch(hashedPassword, currPassword string,
    salt []byte) bool {
  var currPasswordHash = hashPassword(currPassword, salt)

  return hashedPassword == currPasswordHash
}

func main() {
  // Generate random 16 byte salt
  var salt = generateRandomSalt(saltSize)

  // Hash password using the salt
  var hashedPassword = hashPassword("hello", salt)

  fmt.Println("Password Hash:", hashedPassword)
  fmt.Println("Salt:", salt)

  // Check if passed password matches the original password by hashing it
  // with the original password's salt and check if the hashes match
  fmt.Println("Password Match:",
        doPasswordsMatch(hashedPassword, "hello", salt))
}

Password Hash: c7b714330211d3eddd0b047cde89b6ce618f321532eeb6ebbd0974c0d92097a66a2264a9b42012eb3387fe91f217e2109f2eefa26ee24a9c33e5417365bf07ec
Salt: [192 42 57 120 177 235 67 200 75 110 215 162 5 44 205 20]
Password Match: true

About the Author

Follow me on Twitter at @GregoryAGaines and consider signing up for my newsletter.

What Is the Time Complexity of Arrays.sort() and Collections.sort()

Gregory Gaines — Thu, 07 Apr 2022 21:56:45 +0000

Knowing time complexities are crucial for every software engineer, especially those who want to work at the top tech companies. The time complexity of sorting algorithms is especially important since its the basis for many other algorithms. This article explores the time complexity of Arrays.sort and Collections.sort, so you won't be surprised during your interview like I was.

Same Logic Under the Hood

Collections.sort works on Lists whilst Arrays.sort works on arrays. Inspecting the source reveals that Collections.sort converts the passed List into an array. After the conversion, Arrays.sort is called on the newly allocated array.

{"title": "Collections.sort"}
default void sort(Comparator << ? super E > c) {
  // Convert list into array
  Object[] a = this.toArray();
  // Call Arrays.sort on newly allocated array
  Arrays.sort(a, (Comparator) c);
  ListIterator < E > i = this.listIterator();
  for (Object e: a) {
    i.next();
    i.set((E) e);
  }
}

Time Complexity

As of Java 8, Arrays.sort uses two sorting algorithms. One is a modification of Quicksort named dual-pivot quicksort, the other an adaptation of MergeSort named Timsort. Both have a time complexity of O(n log n), where n is the total number of items in the array.

With a Comparator

The time complexity including the comparator is O(n * (log n) * c), where c is the time complexity of the comparator. By default, Arrays.sort uses a comparator following the natural ordering of the content for an O(1) time complexity. Programmer-defined comparators with little computational work also resolve to an O(1) time complexity.

Let's say you define a comparator that had to search through files for a time complexity of O(f), where f is the number of files. The time complexity for sorting results to O(n * (log n) * (O(f) + O(f)) or O(n * (log n) * O(f)), accounting for the O(f) algorithm that runs on each comparison.

Which Algorithm is Used

The parameter type decides the chosen sorting algorithm. Take note of Arrays.sorts method signatures below.

public static void sort(int[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}  

public static void sort(char[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

public static void sort(float[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

public static void sort(T[] a, Comparator<? super T> c) {
  if (c == null) {
    sort(a);
  } else {
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a, c);
    else
      TimSort.sort(a, 0, a.length, c, null, 0, 0);
   }
}

We learn that Quicksort accepts primitive data types while Timsort accepts generics. The reason being Timsort is a stable sorting algorithm while Quicksort isn't. A stable sorting algorithm means if two items of equal value sit next to each other, they will maintain the same order after sorting.

When dealing with primitive data types, two integers swapping positions doesn't matter since they are essentially equal and you can't notice a difference. On the other hand, when sorting objects, equal objects unnecessarily swapping positions can cause harmful effects. Not to mention objects can contain distinct properties which can identify when a swap is made.

Conclusion

Arrays.sort works an array and Collections.sort works on Lists.
Collections.sort converts the Lists into an arrays, then calls Arrays.sort on it.
Arrays.sort has two different sorting algorithms. Quicksort, a non-stable algorithm, and Timsort, a stable algorithm. Both share a time complexity of O(n log n), where n is the total number of items in the array.
Including the comparator is O(n * (log n) * c, where c is the time complexity of the comparator.
Arrays.sort determines which sorting algorithm to use based on the type of the passed parameter. Quicksort for primitive data types and Timsort for objects.
A stable sorting algorithm means items of equal value stay in the same order after sorting.

Consider signing up for my newsletter or supporting me if this was helpful. Thanks for reading!

About the author.

I’m Gregory Gaines, a software engineer that loves blogging, studying computer science, and reverse engineering.

DEV Community: Gregory Gaines

Emulating PS2 Floating-Point Numbers: IEEE 754 Differences (Part 1)

Terminology

Introduction

Problems With Emulating Floating-Point

Floating-Point Format

The Sign Bit

The Exponent

The Mantissa

Putting It All Together

Representing in Code

Converting Into a Float

Differences from IEEE 754 Standard

NaN Does Not Exist

Infinity Does Not Exist

Denormalized Numbers Do Not Exist

Rounding Mode Is Always Rounding to Zero

Final Thoughts

About the Author 👨🏾‍💻

References

A Letter to Rust Users: Don’t Test Implementation Details (Unit vs. Integration Tests)

Table Of Contents

Howdy Reader 👋🏽

Terminology

Rust Unit and Integration Tests Definition 🛠️

Why You Shouldn't Test Implementation Details 🚫

CalculatorV1.rs

CalculatorV1.rs

Calculator_Test.rs

CalculatorV2.rs

CalculatorV2.rs

Calculator_Test.rs

CalculatorV1.rs

Bonus Content 💰

Final Thoughts 💭

About the Author 👨🏾‍💻

My Attempt at Running a Gameboy Emulator in Google Sheets

Table Of Contents

Howdy Reader 👋🏽

Demo 🎮

What is an emulator 🕹️

Shallow Dive into the Gameboy 🥽

The CPU

Keeping Components in Sync

Enter Google Sheets 📊

The First Road Block

Creating the Sidebar

Integrating the Gameboy

Limitations 🚫

It's Super Slow

No way to queue commands

Final Thoughts 💭

About the Author 👨🏾‍💻

DEV Should Remove the Authors Ability to Hide Comments

Intro 📽️

Stop Using .env Files Now!

Gregory Gaines ・ Sep 19 ・ 4 min read

The Battle Of Comments ⚔️

A taste of the Battle 🛡️

Why the hide feature should be removed 🚫

Final Thoughts 💭

About the Author 👨🏾‍💻

Stop Using .env Files Now!

Table Of Contents

Hello Reader 👋🏽

The problem with .env files 🚫

1. Storing the .env file

2. Updating a secret config

3. Versioning

Config servers to the rescue 🦸‍♂️

Solving: 1. Storing the .env file

Solving: 2. Updating a secret

Solving: 3. Versioning

More Pros of a Config Server ✅

Automatic Secret Rotation

VPC Endpoints

Audit Logs

Final Thoughts 💭

About the Author 👨🏾‍💻

Build Your Own Google Like Autocomplete Using React And JavaScript