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/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
05/21/16

Demystifying Virtual Tables in C++ – Part 1 Trivial Constructors

Introduction

This won’t be an easy read. After each claim I will provide supporting code in both C++ and assembly.

Recently I was working on a particularly sneaky bug. A thing happened to me in C++, that should not be possible under normal circumstances. By normal, I mean that 1+1 is guaranteed to 2; the sun rises in the East and sets in the West; all water is wet and the earth is dry…. Yet is still happened. Namely: the vptr of a fully constructed virtual object was pointing to the virtual table of it’s base class. To debug this particular issue one needs to dive deep into the compiler world and into the dreaded waters of assembly.

I hope that I do not have to point out that when I started I had absolutely no clue what is going on. I knew what virtual pointers do and that the compilers are reasonably smart about them. As every modern software engineer I consulted the web oracle only to realise that there is very little written online. I wanted to know how vptrs and vtables are implemented. Not your typical high level theory explaining how dynamic dispatch works. I wanted to know what makes it tick. And while doing so I might improve the world a bit by sharing my journey. So I hopped on my trusted GDB and rode of to the assembly land.

Continue reading


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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/4/15

HackerRank ‘Chocolate Feast’ Solution

Short Problem Definition:

Little Bob loves chocolates, and goes to a store with $N in his pocket. The price of each chocolate is $C. The store offers a discount: for every M wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Link

Chocolate Feast

Complexity:

time complexity is O(N);

space complexity is O(1)

Execution:

Evaluate the number of wraps after each step. Do this until you have enough wraps to buy new chocolates.

Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int eatenChocolades(int availableCash, int price, int wrapperDiscount){
    int eaten = 0;
    int wraps = 0;
    
    wraps = eaten = availableCash/price;
    
    while (wraps >= wrapperDiscount){
        int newlyEaten = wraps/wrapperDiscount;
        eaten += newlyEaten;
        wraps %= wrapperDiscount;
        wraps += newlyEaten;
    }
    
    
    return eaten;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n,c,m;
    cin>>t;
    while(t--){
        cin>>n>>c>>m;
        int answer=0;
        answer = eatenChocolades(n,c,m);
        cout<<answer<<endl;
    }
    return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/3/15

HackerRank ‘Filling Jars’ Solution

Short Problem Definition:

Animesh has N empty candy jars, numbered from 1 to N, with infinite capacity. He performs M operations. Each operation is described by 3 integers a, b and k. Here, a and b are indices of the jars, and k is the number of candies to be added inside each jar whose index lies betweena and b (both inclusive). Can you tell the average number of candies after M operations?

Link

Filling Jars

Complexity:

time complexity is O(N);

space complexity is O(1)

Execution:

Keep a sum variable. Compute the average at the end.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    n,m = map(int, raw_input().split())

    answer = 0

    for _ in xrange(m):
        a, b, k = map(int, raw_input().split())
        answer += (abs(a-b)+1)*k
    print answer//n

 #include<iostream>
 #include<vector>
 #include<math.h>
 #include<array>
 using namespace std;
 int main()
 {
    long n,m;
    long answer=0,t;
    cin>>n>>m;
    t = m;
    while(t--){
        long a,b,k;
        cin>>a>>b>>k;
        answer = answer + (abs(a-b)+1)*k;
    }
    answer = floor(answer/n);
    cout<<answer<<endl;
    return 0;
 }

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/3/15

HackerRank ‘ACM ICPC Team’ Solution

Short Problem Definition:

You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.

Link

ACM ICPC Team

Complexity:

time complexity is O(N^3);

space complexity is O(N)

Execution:

I generate all teams by brute force.

Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;



int acmIcpc(string &str1, string &str2, int length){
    int topicsKnown = 0;
    for (int i=0; i<length; i++){
        if (str1.at(i) == '1' or str2.at(i) == '1'){
            topicsKnown+= 1;
        }
    }
    return topicsKnown;
}
int main() {
    string str[500] = {};
    int N, M;
    cin>>N>>M;
    for (int i=0;i<N;i++) {
        cin>>str[i];
    }
    
    int maxKnown = 0, teamsCnt = 0;
    
    for (int i=0;i<N-1;i++) {
        for (int j=i+1;j<N;j++) {
            int knownForThisCombo = acmIcpc(str[i], str[j], M);
            if (knownForThisCombo > maxKnown){
                maxKnown = knownForThisCombo;
                teamsCnt = 1;
            } else if (knownForThisCombo == maxKnown){
                teamsCnt += 1;
            }
        }
    }
    
    cout << maxKnown << endl;
    cout << teamsCnt << endl;
    return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/2/15

HackerRank ‘Game of Thrones – I’ Solution

Short Problem Definition:

Dothraki are planning an attack to usurp King Robert from his kingdom. King Robert learns of this conspiracy from Raven and plans to lock the single door through which an enemy can enter his kingdom. But, to lock the door he needs a key that is an anagram of a certain palindrome string.

Link

Game of Thrones – I

Complexity:

time complexity is O(N);

space complexity is O(1)

Execution:

A palindrome must by definition have an even number of letters. The only exception is a string of an odd length (‘aba’) that has exactly one odd letter count.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    string = raw_input()
    found = True
    # Write the code to find the required palindrome and then assign the variable 'found' a value of True or False
    oddCnt = 0
    letterCnt = [0] * 26
    
    for letter in string:
        letterCnt[ord(letter)-ord('a')] += 1
    
    for cnt in letterCnt:
        oddCnt += cnt % 2
        
    if oddCnt > 1:
        found = False

    if not found:
        print("NO")
    else:
        print("YES")

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;


int main() {
   
    string s;
    cin>>s;
     
    int flag = 1;
    
    int oddCnt = 0;
    int letterCnt[26] = {};
        
    for (int i=0; i<s.length(); i++){
        letterCnt[int(s[i]) - int('a')]++;
    }
    
    for (int i=0; i<26; i++){
        oddCnt += letterCnt[i] % 2;
    }
    if (oddCnt > 1){
        flag = 0;
    }
    
    // Assign Flag a value of 0 or 1 depending on whether or not you find what you are looking for, in the given string 
    if(flag==0)
        cout<<"NO";
    else
        cout<<"YES";
    return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
03/1/15

HackerRank ‘Max Min’ / ‘Angry Children’ Solution

Short Problem Definition:

Given a list of N integers, your task is to select K integers from the list such that its unfairness is minimized.

Link

Max Min

Complexity:

time complexity is O(N*log(N));

space complexity is O(N)

Execution:

The unfairness is the distance between K elements in a sorted array.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    n = input()
    k = input()
    candies = [input() for _ in range(0,n)]
    candies.sort()
    min_diff = 1000000000
    ## Write code here to compute the answer using (n, k, candies)

    for i in xrange(n - k + 1):
        min_diff = min(min_diff, candies[i+k-1] - candies[i])
    
    print min_diff

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

int main() {
    /* The code required to enter n,k, candies is provided*/

    int N, K, unfairness = std::numeric_limits<int>::max();
    cin >> N >> K;
    int candies[N];
    for (int i=0; i<N; i++)
        cin >> candies[i];
    
    sort(candies, candies + N);
        
    for (int i=0; i < N - K + 1; i++){
        unfairness = min(unfairness, candies[i+K-1] - candies[i]);
    }
    
    cout << unfairness << "\n";
    return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
02/28/15

HackerRank ‘The Love-Letter Mystery’ Solution

Short Problem Definition:

James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

Link

The Love-Letter Mystery

Complexity:

time complexity is O(N*T);

space complexity is O(1)

Execution:

You process the string from the beginning towards mid and always decrement the higher side.

Solution:
#!/usr/bin/py
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        s = map(int, raw_input().split())
        reductions = 0
    	for i in range(0,len(s)//2):
            reductions += abs(ord(s[i]) - ord(s[-1-i]))
    	print reductions 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int letterMystery(string &str){
    int changes = 0;
    
    int mid = str.length()/2;
    int len = str.length();
    
    for (int i=0; i < mid; i++){
        int diff = abs(int(str.at(i)) - int(str.at(len-i-1)));
        changes += diff;
    }
    
    return changes;
}
int main() {
    string str;
    int t;
    cin>>t;
    for (int i=0;i<t;i++) {
        cin>>str;
        cout << letterMystery(str) << endl;
  }
  return 0;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
12/18/14

Eclipse for C++ Development on Windows 7 64-bit Broken Console

It is the year 2014 and for some reason Eclipse CDT (both 32 and 64bit version) since Ganimede won’t output anything the programmer wants to print to the C++ console. The other side effect is, that it is impossible to start the gdb debugger. This problem has been posted all around the web since 2010 and yet it persists with Luna.

EmptySpace

I was able to compile the source using Eclipse, but had to switch to the Cygwin console and execute the binary manually. Doing this is a tedious process and wastes a lot of time. The bad news is, that I have found no solution for Cygwin. The good news is, that the MinGW linker will accept static gcc libraries linkage. So, for the rest of this guide, I will be assuming that you can use the MinGw GNU. Continue reading


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

Facebooktwittergoogle_plusredditpinterestlinkedin