06/24/16

Demystifying Virtual Tables in C++ – Part 3 Virtual Tables

Introduction

In the previous parts of the series we look at Trivial cases and Non-virtual inheritance. Now, it is time to look at the actual content of the series. I repeat the citation we are verifying here:

Whenever a class itself contains virtual functions or overrides virtual functions from a parent class the compiler builds a vtable for that class. This means that not all classes have a vtable created for them by the compiler. The vtable contains function pointers that point to the virtual functions in that class. There can only be one vtable per class, and all objects of the same class will share the same vtable. [1]

We have shown that classes without a virtual function indeed contain no virtual pointer and no virtual table is constructed. A virtual table is an array of function pointers although other data types are also possible. The layout is generally compiler-specific (or ABI-specific where multiple C++ compilers share an ABI) and somewhat stable. All the virtual function tables are in the memory associated with your process. In case of GDB all your virtual function tables are stored in read-only memory which protects it from unintentional overwrites. The functions themselves (their assembly instructions) are stored in the .text section of the elf binary.

Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/22/16

HackerRank ‘Lisas Workbook’ Solution

Short Problem Definition:

Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters.

  • …..

Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. Given the details for Lisa’s workbook, can you count its number of special problems?

Link

Lisa’s Workbook

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This brute force solution iterates over all pages in the final book keeping track of the page(offset) and chapter it is on. There can only be one special problem per page and therefore I check if there is any problem that would match the criteria.

Solution:
def findPages(N, K, P):
    cnt = 0
    offset = 1
    for chapter in P:
        pages = (chapter + K -1)/K
        for idx in xrange(pages):
            if offset >= (idx * K)+1 and offset <= min((idx+1)*K, chapter):
                cnt += 1
            offset += 1

    return cnt

if __name__ == '__main__':
    N, K = map(int, raw_input().split())
    P = map(int, raw_input().split())
    print findPages(N, K, P)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/21/16

HackerRank ‘Sherlock and The Beast’ Solution

Short Problem Definition:

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, . Sherlock determines the key to removing the virus is to find the largest Decent Number having digits.

Link

Sherlock and The Beast

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

I am presenting two solutions. The naive brute force solution executes in O(N) and passes all the tests. Yet further optimisations and a runtime complexity of O(1) are possible.

When observing the possible output space we realise that there can only be 0, 5 or 10 threes in the output. If there would be 15 threes, it is better to use fives instead. The number of trailing threes can therefore be defined by K = 5*((2*N)%3). Let us plug some numbers into the equation:

  • 1 -> 5*(2%3) = 10 -> INVALID
  • 2 -> 5*(4%3) = 5 -> INVALID
  • 3 -> 5*(3%3) = 0 -> 555
  • 4 -> 5*(8%3) = 10 -> INVALID
  • 5 -> 5*(10%3) = 5 -> 33-33-3
  • 8 -> 5*(16%3) = 5 -> 555-33-33-3
  • 10 -> 5*(20%3) = 10 -> 33-33-33-33-33
  • 15 -> 5*(30%3) = 0 -> 555-555-555-555-555
Solution:
def sherlockBeast(N):
    K = 5*((2*N)%3)
    if K > N:
        return -1
    else:
        return '5' * (N-K) + '3'*K

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeast(n)
def sherlockBeastNaive(N):
    if (N < 3): return "-1" three_cnt = N//3 five_cnt = 0 while three_cnt >=0:
        rem = N - three_cnt*3
        if rem % 5 == 0:
            five_cnt = rem/5
            break
        three_cnt -= 1
        
    if three_cnt <= 0 and five_cnt == 0:
        return "-1"
    
    return "555"*three_cnt + "33333"*five_cnt

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeastNaive(n)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/14/16

Martinkysel.com is now HTTPS

I would like to give a quick shoutout to the folks at Let’s Encrypt that have done a great job at making the web a better place. Do you ask why I care about SSL protected web pages?

Because HTTPS:

  • prevents possible intruders from tampering with the communications between this website and you, my fellow readers. Intruders include intentionally malicious attackers, and legitimate but intrusive companies, such as ISPs or hotels that inject ads into pages.
  • prohibits intrusions. It is possible to exploit unprotected communications and to trick users into giving up sensitive information or installing malware, or to insert their own advertisements into website resources. For example, some third-parties inject advertisements into websites that potentially break user experiences and create security vulnerabilities. It is probably not my case, but the greater Encrypt the web initiative is a cause worth pursuing.
  • protects resources that travel between this website and your browser. Images, cookies, scripts, HTML… they’re all exploitable. Intrusions can occur at any point in the network, including a user’s machine, a Wi-Fi hotspot, or a compromised ISP, just to name a few.

Would you give your PC to a complete stranger in Starbucks and leave? I would not and therefore I will not do the same to my page. I agree that reading some page on the web is different than giving someone access to your Facebook pictures. But is it really? How often do you open web pages over a insecure Wi-fi? Do you trust each and every wire you are connected over?

Letsencrypt is a free SSL certificate authority by the folks from Mozilla, Cisco, Akamai, Facebook and many others. If you own, manage or run a page, give them a try. Make the web a better place.

Without further ado I announce that martinkysel.com is now HTTPS.


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/10/16

Demystifying Virtual Tables in C++ – Part 2 Non-virtual inheritance

Introduction

In this post we will continue our dive into the C++ dynamic dispatch. So far we have verified that gdb does not create a virtual table for simple classes and default constructors [Part 1 Trivial Constructors].

In part 2 we will look at non-virtual derived classes, their construction and memory layout.

When creating a class, instead of writing completely new data members and member functions, the programmer can designate that the new class should inherit the members of an existing class. This existing class is called the base class, and the new class is referred to as the derived class.

I assume that readers have a familiarity with C++. I will not be explaining why a class should be derived from another class neither will I explain assembly in detail. We will verify common knowledge about c++ using the gdb debugger on a 64bit Ubuntu linux machine.

Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin