Posts by Chang Park

Singleton Class

What is Singleton?

Restricts a class to instantiate its multiple objects and allows only one instance that has a control throughout the execution

Required properties: (1) should have only one instance and (2) should be globally accessible

 

Initialization

  • Early Initialization – initialize when the class gets loaded
    • Advantage: Simplicity
    • Disadvantage: it’s always initialized whether it is being used or not.
 
class SingletonClass {
    private static SingletonClass object = new SingletonClass();
    private SingletonClass() {}

    public static SingletonClass getInstance() {
        return object;
    }
}

 

  • Lazy Initialization – initialize only when it is required (general way to create a singleton class)
 
class SingletonClass {
    private static SingletonClass object;
    private SingletonClass() {}

    public static SingletonClass getInstance() {
        if(object == null) {
            object = new SingletonClass();
        } 
        return object;
    }
}

 

Examples of Singleton class

  1. Java.lang.Runtime – every app has a singleton instance of class Runtime to interface
  2. Logger – suitable for single log file generation that can prevent concurrent access
  3. Cache – client apps are able to use in-memory object with global point of reference.

 

References

  • https://www.geeksforgeeks.org/singleton-design-pattern-introduction/
  • https://stackoverflow.com/questions/19068468/what-is-meant-by-early-initialization-of-a-singleton-class-in-java

 

Change file system format: Fat32 -> NTFS

Follow the below steps to change file system format of SD card from Fat32 to NTFS on Linux.

 

1. Check SD card from file system:

$ fdisk -l

2. Unmount the SD card:

$ umount /dev/sdh1

3. Wipe the file system of SD card:

$ sudo wipefs -a /dev/sdh1

$ sudo wipefs -a /dev/sdh

4. Wipe mbr and gpt:

$ gdisk /dev/sdh

Then, type x –>  z

5. Zero the first megabytes:

$ dd if=/dev/zero of=/dev/sdh bs=4M count=10

6. Create new partitions:

$ gdisk /dev/sdh

Then, type n –> ENTER –> ENTER –> ENTER –> 0700 for type 0x0700 (Microsoft basic data) –> w to write to disk

7. Then, format it to NTFS:

$ mkfs.ntfs -f /dev/sdh1

8. Done 🙂

 

 

 

 

OpenGL Rendering Pipeline

Pipeline Overview

OpenGL-managed memory buffers (vertex buffers) contains below two array types

  • Vertex Array – this later projected into screen space, assembled into triangles, and rasterized into pixel-size fragments, and the fragments finally assigned color values and drawn to the frame buffers.
  • Element Array – contains indices of vertex (the order of the index matters when assembling triangles)

 

Vertex shader

  • GPU begins by reading each selected vertex out of the vertex array.
  • Vertex shader calculates the projected position of the vertex in screen space.
  • It can also generate other varying outputs, such as a color or texture coordinates, for the rasterizer to blend across the surface of the triangles connecting the vertex.

 

Triangle assembly

  • Connects the projected vertices to form triangles (3 ways)
    • Take every three elements as an independent triangle
    • Make a triangle strip, reusing the last two vertices of each triangle as the first two vertices of the next
    • Make a triangle fan, connecting the first element to every subsequent pair of elements

 

Rasterization

  • Takes each triangle, and clips it and discards parts that are outside the screen
  • Breaks the remaining visible parts into pixel-sized fragments
  • If vertex had a color value, rasterizer blend those colors across the pixelated surface

 

Fragment shader

  • Gets varying values of vertices after vertex shader and rasterizer steps
  • Outputs color and depth values that then get drawn into the frame buffer
  • Also includes texture mapping and lighting
  • fragment shader runs independently for every pixel drawn, it can perform the most sophisticated special effects.
  • The most performance-sensitive part of the graphics pipeline.

 

Frame buffer

  • Color buffers
  • Depth buffer and stencil buffer filter fragments before drawn to frame buffer
    • Depth testing: discards fragments from objects that are behind the ones already drawn
    • Stencil testing: uses shapes drawn into the stencil buffer to constrain the drawable part of the framebuffer
  • Final color, depth, and stencil values are drawn into corresponding buffers.

 

 

 

References

AR Platforms and Engines

PLATFORMS

ARCore (Google)

  • Supports Android/IOS
  • For rendering, uses OpenGL

ARKit (Apple)

  • For rendering, uses Metal API (previously used OpenGL)

 

Engine or SDK

Unity

  • Cross-platform game engine
  • Supports C#, Javascript, Boo
  • Integration of unity inside android code is painful

Sceneform SDK

  • Google’s 3D framework (released 2018)
  • Sceneform APIs help to develop ARCore apps (e.g., detecting plane, lights estimation)
  • No need to learn 3D graphics or openGL

Vuforia SDK

  • Uses ARCore/ARKit if the running device supports it. If not, it runs own AR technology and engine.
  • Can be used in Unity

 

 

 

Trusted Thread Scheduling in OP-TEE

Trusted thread for standard services (standard SMC)

  • Terminates when optee_os returns to the normal world with a service completion status.
  • Can be interrupted by
    • Foreign interrupt (non-secure): optee_os suspends the trusted thread and invokes the normal world through the Monitor (RPC services). The trusted threads will resume only once normal world invokes the optee_os with the RPC service status.
    • Native interrupt (secure): Native interrupt is handled by the interrupt exception handler. Once served, optee_os then returns to the execution of trusted thread.
  • Can lead optee_os to invoke a service in normal world (e.g., access a file, get the REE current time, etc.).
    • Trusted thread is suspended/resumed for the remote service execution.

 

Scheduling consideration

  • When interrupted by foreign interrupt or optee_os invokes a normal world service, the normal world gets the opportunity to reschedule the running application. The trusted thread can resume only once the client application is scheduled back. That means a trusted thread execution follows the scheduling of the normal world.
  • optee_os does not implement any thread scheduling. Each trusted thread is expected to track a service that is invoked from the normal world and should return to it with an execution status.
  • Linux thread invoking OP-TEE gets assigned a trusted thread on TEE. So trusted threads are scheduled by the linux kernel.

 

Trusted thread constraints

  • TEE handles a static number of trusted thread (CFG_NUM_THREADS).
  • Trusted threads are only expensive on memory constrained system, mainly regarding the execution stack size.
  • On SMP (Systematic Multi-Processing) system, optee_os can execute several trusted threads in parallel if the normal world supports scheduling of processes. UP system, supporting several trusted threads in optee_os, also helps normal world scheduler to be efficient.

 

 

Source:

Interrupt Handling in OP-TEE

Basics

  • World switches through Secure Monitor Call (SMC).
  • A secure interrupt is signaled by the ARM GIC (Generic Interrupt Controller).
  • There are two types of interrupts.
    • IRQ: Foreign interrupt (non-secure)
    • FIQ: Native interrupt (secure)
  • Each world has own interrupt exception vector.
  • When an interrupt is in same world, it directly handles the interrupt.
  • When an interrupt is in different world, it switches a context (by Monitor vector) to the corresponding world first and then handles the interrupt.

Overview of Interrupt Handling

 

Standard SMC

Normal world invokes optee_os using SMC

  • On every context switching, it saves a state of current world and restores a previous state of an other world. (normal – secure)
  • Fast SMC: Blocks all IRQ/FIQ exception until it returns back to normal world.
  • Standard SMC: After assigning a trusted thread (core/arch/arm/kernel/thread.c),
  • Both fast SMC and standard SMC end on the entry stack with IRQ/FIQ blocked.

SMC entry to secure world

 

Multiple cases of IRQ & FIQ

  • Explanations on this section is based on GICv2, and details about GICv3 are discussed on the bottom of this post.

Non-secure interrupts (IRQ) on Secure World (SCR_NS = 0)

  1. Saves trusted thread context
  2. Blocks all interrupt (IRQ and FIQ)
  3. Switches to entry stack
  4. Restores normal world context with a return code indicating that an IRQ is about to be delivered
  5. After handling IRQ, normal world issues a new SMC to return and to finish last SMC.

IRQ received in secure world and forwarded to normal world

 

Non-secure interrupts (IRQ) on Normal World (SCR_NS = 1)

  • IRQ will be delivered using the state vector (VBAR) in the normal world.
  • The monitor and the Trusted OS are not involved at all.

 

Secure interrupts (FIQ) on Normal World (SCR_NS = 1)

  1. Saves normal world context and restores previous secure world context
  2. Clears SCR_FIQ when clearing SCR_NS
  3. Sets “FIQ” as parameter to secure world entry and returns to secure world
  4. Secure world unmasks FIQs because of the “FIQ” parameter.
  5. FIQ is received as an exception in the state vector, and the state vector handles and returns the exception.
  6. Secure world issues an SMC to return to normal world
  7. Monitor saves secure world context and restores normal world context.
  8. Return from exception to normal world

FIQ received when SCR_NS is set

 

Secure interrupts (FIQ) on Secure World (SCR_NS = 0)

  • FIQ will be delivered using the state vector (VBAR) in the secure world.
  • The monitor is not involved at all.

 

Secure Interrupts (FIQ) received while processing Non-secure Interrupts (IRQ) forwarded from Secure World

  • FIQ has higher priority than IRQ.
  • While processing IRQ, the context switches back to secure world to handle FIQ. After FIQ is completely handled, it switches back to normal world to finish IRQ.

FIQ received while processing an IRQ forwarded from secure world

 

Generic Interrupt Controller (GIC)

GIC is an architected resource that supports and controls interrupts.

  • GICv2: supports ARMv7
  • GICv3: supports ARMv8-A (Hikey960)
    • New features added to scale a large system (GICv2 handles only 8 processing elements)
      • Affinity routing (Interrupt routing)
      • Redistributor (Interrupt distribution)
  • GICv4: extension of GICv3

 

Important differences between GICv2 and GICv3

  • GICv2: native interrupt is sent as FIQ and foreign interrupt is sent as IRQ.
  • GICv3: foreign interrupt is sent as FIQ which could be handled by either secure world (aarch32 Monitor mode or aarch64 EL3) or normal world. ARM GICv3 mode can be enabled by setting (CFG_ARM_CIV3=y).

 

Source:

 

Sorting Algorithms

Time complexity of sorting algorithms

 

Selection Sort – Youtube Link

  • From the beginning of an array, it finds minimum element in unsorted subarray (right side) and puts the element at the end of sorted subarray (left side) until it gets to the end.

e.g. Given unsorted array: 64  25  12  22  11. Red colored number is minimum in unsorted subarray, and underline represents a sorted subarray.

     64  25  12  22  11

     11  25  12  22  64

     11  12  25  22  64

     11  12  22  25  64

     11  12  22  25  64   (Completed)

 

Bubble Sort Youtube Link

  • It repeatedly swapping the adjacent elements if they are in wrong order.

e.g. Given unsorted array: 5  1  4  2  8. Two red colored numbers get compared and swapped.

   [ 1st Pass ] 

      5  1  4  2  8

     1  5  4  2  8

     1  4  5  2  8

     1  4  2  5  8

   [ 2nd Pass ]

     1  4  2  5  8

     1  4  2  5  8

     1  2  4  5  8

     1  2  4  5  8

Now the array is sorted, but it goes one more step checking whether whole pass doesn’t have any swap.

   [ 3rd Pass ]

     1  2  4  5  8

     1  2  4  5  8

     1  2  4  5  8

     1  2  4  5  8

 

Insertion Sort Youtube Link

  • It works the way we sort playing cards in our hands.
  • From the beginning of an array, next element gets compares with numbers from the end of sorted subarray and gets placed in right position.

 

Heap Sort Youtube Link

  • It builds a max heap (a parent node is larger than all children nodes) from the input data.
  • It is similar to selection sort, but it finds max instead of minimum. However by using max heap, sorting time is faster than selection sort.

 

Quick Sort Youtube Link

  • It is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
    1. Always pick first element as pivot.
    2. Always pick last element as pivot.
    3. Pick a random element as pivot.
    4. Pick median as pivot.

    The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

 

Merge SortYoutube Link

  • It is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.
    • merge(): merging two halves, O(n).
    • Mergesort(): recursively calls itself to divide the array till size becomes one, O(logn).

 

 

Source:

P vs. NP

The P vs. NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified (technically, verified in polynomial time) can also be solved quickly (again, in polynomial time).

P (Polynomial Time)

  • Some algorithm can provide an answer in polynomial time (opposed to exponential time).

NP (Nondeterministic Polynomial Time)

  • There is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly (in polynomial time).
  • E.g. Sudoku – Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger.

NP – Complete

  • A problem in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.
  • It is not known whether every problem in NP can be quickly solved—this is called the P vs. NP problem. But if any NP-complete problem can be solved quickly, then every problem in NP can be solved quickly because of above definition.

 

P = NP: Problems that can be verified in polynomial time can also be solved in polynomial time.  

P ≠ NP: Problems can not be solved in polynomial time, but the answer could be verified in polynomial time.

 

Here is a helpful Youtube video.

 

 

 

Sources:

 

How to create custom framework APIs

aosp

On this post, we will learn how to modify or create framework APIs on AOSP (Android Open Source Project).

Before start, let’s set a build environment and download AOSP source codes. Please follow steps on these links (environment and source code).

  • Make sure that you have at least 200GB of a free space.

 

Path to Work on

…/framework/base contains all framework libraries and APIs that we used to develop an app, e.g., android.app.Activity. So, all of our work will be done under this path either to modify existing framework APIs or to create new framework APIs.

(Will be updated) Framework APIs

(Will be updated) JNI (libraries)

 

Files Generated

After done with modifications, please follow these steps to build. Then, you will see these three  files generated.

Under <aosp-root>/out/target/product/<product-name>/system/framework/,

  • framework.jar: APIs accessible to applications
  • services.jar: Implementation of managers and system services located under frameworks/base/services.

Under <aosp-root>/out/target/product/<product-name>/system/lib/,

  • libandroid*.so: Libraries generated from native code (C/C++) like the .cpp files located at frameworks/base/core/jni.

 

Using Modified Framework APIs

After modification, we want to use the new framework APIs while building an app. However, current version of framework APIs that our machine uses is not updated yet. That means  our IDE cannot find the APIs. So, please replace files under ~/Library/Android/sdk/platforms/android-{version #}/This path can be different on your machine.

 

Frameworks supporting to develop cross-platform mobile apps

cross-platform-app

Recently, multiple frameworks support developing cross-platform mobile apps. This means developers can reuse the written code on different platforms using these frameworks, and it helps to reduce costs significantly. On this post, I will talk about the differences between these popular frameworks.

Four popular frameworks

There are four popular frameworks which are Flutter, Xamarin, ReactNative, and Titanium. For easier understanding, I drew a comparison table.Screen Shot 2018-07-01 at 2.51.05 PMXamarin, ReactNative and Titanium are similar but using different languages. Flutter is the latest framework from Google, and its key feature is providing full UI stack implementation without using native UI components. This means UIs will be exactly the same on different platforms. Other three frameworks link with original framework, and that means UIs will be slightly different on different platforms. Also, Flutter is fast and smooth because of no need for linking with original frameworks.

Integrating with third party libraries

Class-form supporting frameworks usually have issues with integrating third-party libraries. Complex apps use multiple third-party libraries, and this limitation is critical. However, Flutter supports linking Flutter APIs with third-party libraries, and those codes using third-party libraries should be written in specific languages of the libraries. That means these codes cannot be reused across other platforms.

Common misunderstanding

A lot of people get confused with characteristics of ReactNative, Titanium, Ionic, PhoneGap and Cordova. Even though they all use JavaScript, they are different. ReactNative and Titanium are frameworks for developing cross-platforms and link JavaScript with original frameworks. They do not use WebView. However, Ionic,PhoneGap and Cordova use WebView and also have native source codes. These are called hybrid apps.

Ionic, PhoneGap and Cordova are sometimes called frameworks for class-platform because they use html, css and JavaScript which are class-platform.